gotchaMinor
Why does everyone say that NFA guesses it's next state?
Viewed 0 times
whyguessesnfaeveryonesaynextthatstatedoes
Problem
In the picture above e is an empty string, and a is a symbol from an alphabet. Every book or professor I have heard from, says than when we make transitions in the NFA, the NFA must guess which state to go to next. In the example above, the NFA must guess whether it should go left or right.
Why do they use the word guess? I have written a simple regular expression engine once and used dfs to go both right then left, if the right path didn't lead to a final state.
Why do they use the word guess? I have written a simple regular expression engine once and used dfs to go both right then left, if the right path didn't lead to a final state.
Solution
There are many equivalent ways to describe the operation of an NFA. One is using guesses. If you don’t like it, I suggest not using it.
Guesses come up very naturally in the union construction. Suppose we are given NFAs for two languages $A,B$. We create a new NFA with a new initial state which points to the initial states of the NFAs for $A,B$, with $\epsilon$-transitions. When considering the semantics of the new NFA, it is natural to think of the NFA as first “guessing” which of the two $\epsilon$-transitions to take initially — this amounts to guessing whether the input belongs to $A$ or to $B$.
An NFA accepts a given input word if it can work its way from the initial state to an accepting state, following the input symbols and using $\epsilon$-transitions at will. Tracing the operation of the NFA, at a given point there might be many possible transitions to take, and the NFA has to choose one of them. If the input belongs to the language of the NFA, then there must exist a set of correct choices which leads the NFA to an accepting state. We refer to the process in which the NFA chooses an accepting path by the name guessing. This is a metaphor which many people find helpful, but if you don’t, feel free not to use it.
Guesses come up very naturally in the union construction. Suppose we are given NFAs for two languages $A,B$. We create a new NFA with a new initial state which points to the initial states of the NFAs for $A,B$, with $\epsilon$-transitions. When considering the semantics of the new NFA, it is natural to think of the NFA as first “guessing” which of the two $\epsilon$-transitions to take initially — this amounts to guessing whether the input belongs to $A$ or to $B$.
An NFA accepts a given input word if it can work its way from the initial state to an accepting state, following the input symbols and using $\epsilon$-transitions at will. Tracing the operation of the NFA, at a given point there might be many possible transitions to take, and the NFA has to choose one of them. If the input belongs to the language of the NFA, then there must exist a set of correct choices which leads the NFA to an accepting state. We refer to the process in which the NFA chooses an accepting path by the name guessing. This is a metaphor which many people find helpful, but if you don’t, feel free not to use it.
Context
StackExchange Computer Science Q#95820, answer score: 5
Revisions (0)
No revisions yet.