Computation – An NFA to a DFA

Non-Deterministic Finite Automata (NFA)

So now you’ve seen a slight introduction into DFAs, its time to introduce their counterpart – NFAs! Now as seen from above, a DFA can sometimes be relatively simple to draw, however, sometimes it can be even easier to draw an NFA.



An NFA is basically means that from some states, there may be several edges coming from that state all labelled with the same letter. This is obviously unlike a DFA, which from any state, can only have precisely one state with a letter.

Let’s look at an exam NFA:



OK, now from this, say you were in state 1. Now, in this state, say the next letter in some given word is a ‘1’, what would you do? Well, you can do 1 of 2 things:

1. Go from state 1, loop round and be back in state 1. or


2. Go from state 1, and end up in state 2.

You may think that this will not accept some words when it should. However, for our purposes, it is good enough if there is at least one such path that ends as an accepting state.

Defining an NFA

It is clear from the diagram above that an NFA does have the same set of states as a DFA, which is the set Q. From this we can also see that there are also still the most important accepting states set, as well as the start state: q• and F.

However, the transition function that a DFA had no longer exists – why? Because, we now have an NFA, with multiple edges sharing the same letter. Therefore, the transition function for a DFA, becomes a transition relation for an NFA. In this case, given a state q and a letter x, and another state q’, it is possible to use the relation δ to tell use whether or not there is an edge labelled with the letter x, that can take us from states q to q’. And now, its definition time again :)

———————————————————————————————–

Definition 11: A non-deterministic finite automaton is given by a finite non-empty set Q, a start state q•, and a subset of Q, which is F – the set of accepting states.  Then we have the transition relation, δ.

Definition 12: A given word, over an alphabet is accepted by the NFA, if there are states:

• qo = q•, q1 ….. qn

Such that for all 0 ≤ i < n, δ relates (qi, xi) to qi+1, and such that qn Є F. And that qn is an accepting state. The language recognized by an NFA is the set of all words it accepts.

———————————————————————————————–

Also, it is probably wise to note something down here. In the definitions of an NFA, unlike in a DFA, there is no rulethat says that for each given state, there must be an edge for every letter. So in this case, if you end up in a state, and there is no letter out of that state to another given state, then the word is not accepted.

NFA vs. DFA

So far we have found the following deference’s between DFAs and NFA automata: For the same problem it is usually easier to design an NFA, and the resulting automata are often smaller. On the other hand, following a word through a DFA automaton is straightforward, and so deciding whether the word is accepted is easy. For an NFA we have to find all the possible paths a word might move along, and decide whether any of them leads to an accepting state. Hence finding the language recognized by an NFA is usually harder than to do the same thing for a DFA of a similar size. However, anything we can do with an NFA, we can also do with a DFA. Hence we can say:

For every NFA there is a DFA that recognizes precisely the same words

Let’s have an example. Consider the following NFA.



OK, so how do we make this NFA into a DFA? Well, it’s relatively simple actually. It only involves a few steps:

1. Copy the start state. In this case its state 0, which also happens to be an accepting state, so our new automaton so far looks like this:
   
   


2. OK, so now we look at state 0 carefully, and say “which states can I get to from state 0 with an ‘a’?” In this case, states 1 and 2. So we create a new state called 12. Since state to is an accepting state,  then we make state 12 an accepting state as well:
   
   


3. Now we do the same thing for the letter ‘b’ in state 0. This time we can only go to state 1, and since state 1 isn’t accepting, then our new state is also, not accepting:
   
   


4. So, let’s start with the next state, state 1, as well as the new state, state 1. Here we can obviously see that using the letter ‘a’ wont get us very far. So let’s try a ‘b’ instead. Ah, we can move. In fact, from state 1 with a ‘b’ we can go to a new state, state 2 – which is accepting as well:
   
   


5. Now we do the same for state 12. Here using an ‘a’ still wont get use very far, not just for state 1, but state 2 as well! So let’s try a ‘b’. Now were getting somewhere. With a ‘b’ we cant get anywhere from state 2, but we can get from state 1 to state 2. So our finishing DFA is:
   
   

There is the final automaton. However, as you may have hopefully noticed, the automaton does not follow one rule that governs a DFA!

That’s right, states 12 and 1 need to have an edge labeled ‘a’, and the state that they lead to will bet the empty set, Ø. However, state 2 also needs an edge labeled ‘a, b’, and this will loop round, back to state 2.

So our FINAL automaton looks like this:



Next is forming patterns from automatons.