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??
可以将文章内容翻译成中文,广告屏蔽插件可能会导致该功能失效(如失效,请关闭广告屏蔽插件后再试):
问题:
回答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