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

  • Thread starter Thread starter evinda
  • Start date Start date
AI Thread Summary
The discussion revolves around the equivalence of NFAs with and without ε-moves, focusing on the necessity of adding transitions in the absence of ε-transitions. Participants analyze how to transition between states while consuming symbols, particularly questioning the need for a transition on '1' from state q0 to q1 when no direct transition exists. They clarify that in the new NFA without ε-transitions, certain transitions must be added to maintain equivalence. The conversation concludes with an understanding of how transitions are modified and the implications for reading specific input sequences. The participants express satisfaction with their resolution of the topic.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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$?
 

Attachments

  • ep.JPG
    ep.JPG
    43.3 KB · Views: 102
  • ep2.JPG
    ep2.JPG
    6.3 KB · Views: 108
Physics news on Phys.org
evinda said:
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)
 
Last edited:
I like Serena said:
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?
 
evinda said:
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)
 
I like Serena said:
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)
 
evinda said:
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)
 
I like Serena said:
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
 

Attachments

  • nfa.JPG
    nfa.JPG
    19.6 KB · Views: 98
evinda said:
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$.
 
I like Serena said:
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?
 

Attachments

  • init.png
    init.png
    2.7 KB · Views: 100
  • #10
evinda said:
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)
 
  • #11
I like Serena said:
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)
 
  • #12
evinda said:
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)
 
  • #13
I like Serena said:
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)
 
Back
Top