In the last post, I mentioned the fact that regular expressions specify the same set of languages as regular grammars, and that finite state machines are the computational device that can recognize those languages.
It’s even pretty easy to describe how to convert from regular expressions to FSMs. But before we do that, to make it a bit easier, we’ll extend our finite state machines. Doing that is interesting in itself: What we’re going to do is create non-deterministic finite state machines – NFA (for nondeterministic finite automata) for short.
NFA are interesting things. They’re a variation on the deterministic state machines (DFA) that we looked at before. An NFA is pretty similar to the DFA, except that the machine is allowed to make choices.
In the formulation that I’m using, there are two key differences between DFAs and NFAs:
- Multiple Transitions/Choices
- There can be more than one transition from a given state on a given input symbol.
- Empty transitions
- Two states in an NFA can be connected by an edge labelled . This is called a null transition.
The non-deterministic machine runs in pretty much the same way as a deterministic machine except:
- If there is a null transition from a state, then a machine in that state can take the transition any time that they want, without consuming any inputs.
- If there is more than one transition from a state on a particular machine, the machine can choose any of the available transitions.
A non-deterministic machine accepts an input string if there is any possible way of running the machine on a string that ends in a final state. For example:
This machine contains one transition labelled with an , meaning that the transition can be taken from without consuming any input.
So – the interesting question that NFAs bring up is: does changing the machine this way do anything? Does it give us any more power? Unfortunately, no. Given a non-deterministic FSM, we can easily convert it to a deterministic FSM.
- The DFA will have one state For each member of the powerset of the states of the NFA.
- The initial state of the DFA is the same as the initial state of the NFA.
- A state in the DFA is final if any of its members is a final state in the NFA.
- For each state and each input symbol , there is a transition to state if there are sequences of empty transitions surrounding a single non-empty transition for from members of to members of in the NFA.
Basically, what that means is that you can create a DFA which superimposes every possible state that the NFA could be in. After any input string has been consumed, the state of the DFA is the set of states that the NFA could have been in after seeing that string.
So, for example, the NFA shown above can be converted into the following DFA:
We start with . From , if we see an “a”, there are three things that could happen. Either we’d take the transition to , or we’d take the empty transition to , and then take the transition from to , or we’d take the empty transition to , and then take the a-transition to . So in the DFA, we’d have an a-transition from to .
If we saw a , there are no transitions shown. By convention, we assume some “invisible” states. Any time that there’s no transition listed for a given input symbol from a state, we assume that there’s a transition from the state to “error”. But we can use that assumption in the DFA as well as the NFA – so we just won’t show the error state or transitions – that makes our machines much easier to read.
Analyzing state has given us state . If we see an input of a, that could bring us to or (if the NFA was in state ); or it could bring us to state (if the NFA was in state .) So for an input of a, we’d put a transition to state . If we saw an input of “b”, we could either go from to , or from to . So for b, we’d have a transition to .
And so on – the final result being:
What does this mean?
Well, a NFA isn’t more powerful than a deterministic machine (a DFA)- there’s nothing that an NFA can do that a DFA can’t. But the NFA can do it with a lot fewer states. The DFA is a lot more complicated; it can have exponentially more states. But for an NFA, there’s a corresponding DFA that can recognize the same language.
Most importantly… it means that with a fixed, finite amount of state, non-determinism doesn’t buy you any computational power. With a finite state machine, non-determinism can’t doesn’t even make it possible to do anything faster! The only benefit that non-determinism has at this level is space: the amount of state that you need (that is, the number of states in the machine) can be smaller with a non-deterministic machine.