time complexity trade offs of nfa vs dfa

Question

I am looking for a discussion on which is better used and in what circumstances in a compiler an nfa or dfa. what are the time complexity trade-offs of simulating an nfa vs dfa and which one is more suitable during what circumstances in a compiler??

Shari

i found the answer for anyone else looking.. – Shari

Time-Space Tradeoffs Goal: Given reg. exp.r and input stringx, determine whetherx is in L(r) Method #1: Build NFAN fromr using Thompson's construction, then run previous algorithm ¡ Can construct NFA inO(|r|) time. ¡ N has at most twice as many states as |r|, and at most two transitions from each state, so transition table isO(|r|) space. ¡ Previous algorithm accepts or rejectsx inO(|r|×|x|) time – Shari

Method #2: Build NFAN fromr using Thompson's construction, then DFAD fromN using subset construction; then use DFA algorithm from last time for accepting/rejectingx ¡ D can have up to 2k states, where k = # states in N. ''Worst- case'' string (a |b)*a (a |b)(a |b)...(a |b) : why? ¡ DFA acceptance algorithm accepts or rejectsx inO(|x|) – Shari

Summary: Automaton Build Run NFA O(|r|) O(|r|×|x|) DFA O(2|r|) O(|x|) So use first method (NFA) for quick search over short text strings (e.g., emacs r.e. search) Use second method (DFA) for longer searches over long text strings (e.g., Unix grep on multiple files) ''Lazy'' DFA method builds DFA transition table on the fly, caching transitions as state/input pairs are encountered – Shari

I understand that the number of states in a DFA constructed from an NFA with $r$ states could be up to $2^r$, but I don't understand how the cost of building a DFA from an NFA with $r$ states costs $O(2^r)$. What about the cost of adding edges on each input symbol the the DFA? Is $O(vertices) = O(edges)$ for the constructed DFA? – Bipropellant

Answer 1

• The construction time for a DFA from an NFA is O(2^m) where m is the number of nodes.
• The running time of a DFA is O(n) where n is the length of the input string. This is because there is only 1 path through the DFA for a given string.
• The construction time for an NFA should be O(m), where m is the number of nodes
• The running time for an NFA is O(m²n) because it is non-deterministic and the computer must check every possible path for the current character in the string. (assuming no lookahead, it doesn't know what the next character will be so it runs into dead ends)

These figures might give u a brief idea

Faletti

Running an NFA via backtracking, as you seem to suggest, will take O(2^n) in the worst case. Luckily there are smarter algorithms that take O(mn) time, though they don't support backreferences. (One implementation is Google's re2.) – Isiah

Very interesting, thank you. I wonder why the same reasoning doesn't apply to Turing Machines vs Non-deterministic Turing Machines. – Nickelson