Equivalence of NFAs with/without $\epsilon$-Moves

[evinda]

Hello! (Wave)

I am looking at the equivalence of NFAs with $\epsilon$-moves to NFAs without $\epsilon$-moves.

View attachment 5767

View attachment 5768

Why do we have to add a transition on $1$ from $q_0$ to $q_1$ although we don't have an arrow from $q_0$ to $q_1$ that corresponds to the symbol $1$?

 

[I like Serena]

Hello! (Wave)

I am looking at the equivalence of NFAs with $\epsilon$-moves to NFAs without $\epsilon$-moves.Why do we have to add a transition on $1$ from $q_0$ to $q_1$ although we don't have an arrow from $q_0$ to $q_1$ that corresponds to the symbol $1$?

Hey evinda! (Smile)

Let's see how we can get from $q_0$ to $q_1$ while consuming a symbol... (Thinking)

Isn't that the following?
$$q_0 \overset 0\to q_0 \overset \varepsilon\to q_1 \\
q_0 \overset \varepsilon\to q_0 \overset 1\to q_1$$

Actually we can also pass $q_1$ by with only epsilons:
$$q_0 \overset \varepsilon\to q_1 \overset \varepsilon\to q_2$$
We'll have to consider that later to see what can happen afterwards when a symbol is consumed after all. (Sweating)

 

[evinda]

Isn't that the following?
$$q_0 \overset 0\to q_0 \overset \varepsilon\to q_1 \\
q_0 \overset \varepsilon\to q_0 \overset 1\to q_1$$

Shouldn't the second one be as follows?$$q_0 \overset \varepsilon\to q_1 \overset 1\to q_1$$

Or am I wrong?

 

[I like Serena]

Shouldn't the second one be as follows?$$q_0 \overset \varepsilon\to q_1 \overset 1\to q_1$$

Or am I wrong?

Yep. You're right. (Nod)

 

[evinda]

Yep. You're right. (Nod)

That's why I haven't understood why we have to add a transition on $1$ from $q_0$ to $q_1$... (Sweating)

 

[I like Serena]

That's why I haven't understood why we have to add a transition on $1$ from $q_0$ to $q_1$... (Sweating)

In the original NFA that is not possible, but we are revising it into a different NFA without $\varepsilon$-transitions.
In the new NFA we will have the same states with different transitions such that there will not be $\varepsilon$-transitions any more.
So we replace the 2 transitions that include a $\varepsilon$-transition with 1 transition. (Emo)

 

[evinda]

In the original NFA that is not possible, but we are revising it into a different NFA without $\varepsilon$-transitions.
In the new NFA we will have the same states with different transitions such that there will not be $\varepsilon$-transitions any more.
So we replace the 2 transitions that include a $\varepsilon$-transition with 1 transition. (Emo)

I think that I got it... But then at the following, why don't we also add a transition on $0$ from $q_1$ to $q_2$ ?

View attachment 5774

 

[I like Serena]

I think that I got it... But then at the following, why don't we also add a transition on $0$ from $q_1$ to $q_2$ ?

I see this is a slightly different NFA than in the opening post.
Once we're in $q_1$ or $q_2$ there is no transition on $0$ any more is there? (Wondering)
We do have a transition on $0$ from $q_0$ to $q_2$.

 

[evinda]

I see this is a slightly different NFA than in the opening post.
Once we're in $q_1$ or $q_2$ there is no transition on $0$ any more is there? (Wondering)
We do have a transition on $0$ from $q_0$ to $q_2$.

The NFA with $\epsilon$-moves that we have is the following, isn't it?

View attachment 5777

So couldn't we read 0 more than once at the beginning and then twice $\epsilon$ ?
That's why I thought that we could add a transition on 0 from $q_1$ to $q_2$.
So I am wrong, right?

 

[I like Serena]

The NFA with $\epsilon$-moves that we have is the following, isn't it?

So couldn't we read 0 more than once at the beginning and then twice $\epsilon$ ?
That's why I thought that we could add a transition on 0 from $q_1$ to $q_2$.
So I am wrong, right?

Yes. That's the NFA with $\epsilon$-moves.

Wouldn't that then be a transition from $q_0$ to $q_2$? (Wondering)

 

[evinda]

Yes. That's the NFA with $\epsilon$-moves.

Wouldn't that then be a transition from $q_0$ to $q_2$? (Wondering)

Yes, that's right... I thought so, because this case also appeared at the NFA of my first post.

So couldn't we also remove the transition on 0 from $q_1$ to $q_2$ at the corresponding new NFA of my first post? Or am I wrong? (Sweating)

 

[I like Serena]

Yes, that's right... I thought so, because this case also appeared at the NFA of my first post.

So couldn't we also remove the transition on 0 from $q_1$ to $q_2$ at the corresponding new NFA of my first post? Or am I wrong? (Sweating)

But in the OP we can go $q_1 \overset\epsilon\to {q_2} \overset 0\to q_2$ can't we? (Wondering)

Suppose we remove it, can we read for instance $010$ then? (Wondering)

 

[evinda]

But in the OP we can go $q_1 \overset\epsilon\to {q_2} \overset 0\to q_2$ can't we? (Wondering)

Suppose we remove it, can we read for instance $010$ then? (Wondering)

I think that I got it now... Thanks a lot! (Mmm)