4
$\begingroup$

enter image description here

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.

$\endgroup$

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Consider the NFA in your picture, which finds all the strings which are repeats of "a" which are a multiple of two or three long. The left branch is for multiples of three, the right for multiples of two. It should be clear how these $\epsilon$-transitions can be used to "join" together those two smaller automata to build this expression.

Now say you are running the algorithm, and you have received a certain number of a's. You don't know at this point which branch you "should" be in. The two sides cannot be somehow "merged" as we don't allow mixtures of pairs and triples: it needs to recognise either "all pairs" or "all triples" and at the start we don't know: it's undetermined, hence non-deterministic finite automaton.

There are many ways to implement non-determinism and it's not really important in the description of NFAs which you choose, so it's not specified. The NFA description is more abstract than that.

  • The most convenient for theoretical construction is the "perfect guesser", the lucky dude. If you can manage to put aside the idea that this is not directly implementable, this carries the least baggage and complexity into the discussion, except discussion about implementation (for example, discussion about construction).
  • Another way to look at it is the possibility of acceptance. Imagine that the accept state executes some terrible deed (sets off a bomb, or something), and the implementation follows any epsilon transitions just randomly. You've been asked as a safety expert whether it's possible that the deed would be performed for a given string. You have to assume the "worst case" to do this. There's no "magic" involved in this analogy, so you might prefer this approach.
  • One slightly practical means of implementing an NFA is to allow parallel execution. At each branch point both are considered by different threads (etc). At the end the threads are collected and the algorithm looks to see if any are successful.
  • Another, more practical means is by back-tracking decisions you've made to choice points. This is the same thing as exploring a search-space by depth-first search. This seems to be what you implemented.
  • It's also possible to just "put a counter" on every state you might be in at any point in time as you go through a string (when there's an $\epsilon$-transition new counters go on all states at the other end of it). At each step move on all the counters and see if any counter ends up in the accept state at the end.
  • It's possible to extend this approach to build a DFA, without all this $\epsilon$ annoyingness. A downside to doing that is that the DFA could be vastly bigger than the NFA; the upside is that it rarely is and sometimes is smaller. (There are other practical downsides to the DFA route, too). This algorithm is called the powerset construction.

Given all this complexity, when you're talking about (say) building an NFA from a regular expression, it's usually best just to ignore these details and just assume luck (good or bad).

In my experience, people who are more anxious and pessimistic (seemingly, an increasing proportion) often have a distracting emotional reaction to the idea of the "lucky guy" interpretation, and I've found that it's often best to go with the "possibility of doom" (safety guy) explanation when first introducing it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.