[prev] [prev-tail] [tail] [up]

3 NFAs are no better than DFAs!

Given an NFA, there exists a DFA that accepts the same language. This means that NFAs are not more powerful or expressive than DFAs. However, NFAs can be more elegant with far fewer states compared to a equivalent DFA (to accept the same language).

Let us start with an NFA M = (S,Σ,T,s,A). We can construct a equivalent DFA M′ = (S′,Σ,T′,s,A′) as specified in the pseudocode of listing 1.


Listing 1: nfatodfa
 
1S′=P(S) 
2for each r∈S′ do 
3  for each σ∈Σ do 
4    u←{} 
5    for each x∈ r do 
6      if ∃(x,σ,y)∈T then 
7        u←u∪y 
8      end if 
9    end for 
10    T′←T′+ (r,σ,u) 
11  end for 
12  if ∃w∈r:w∈A then 
13    A′←A′+r 
14  end if 
15end for 
16for each r∈ S′ do 
17  if ¬(∃(r,σ,u)∈T′) then 
18    S′←S′−r 
19  end if 
20end for

[prev] [prev-tail] [front] [up]