7

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??

Lilly_Code
  • 150
  • 1
  • 8
  • i found the answer for anyone else looking.. – Lilly_Code Jan 10 '11 at 19:44
  • 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 – Lilly_Code Jan 10 '11 at 19:44
  • 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|) – Lilly_Code Jan 10 '11 at 19:45
  • 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 – Lilly_Code Jan 10 '11 at 19:45
  • 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? – dhruvbird Nov 24 '13 at 20:53

1 Answers1

6
  • 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

Nihal Rp
  • 484
  • 6
  • 15
  • 2
    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.) –  Aug 31 '15 at 11:16
  • Very interesting, thank you. I wonder why the same reasoning doesn't apply to Turing Machines vs Non-deterministic Turing Machines. – étale-cohomology Jun 28 '22 at 08:31