LEXICAL ANALYSIS
REGULAR EXPRESSIONS AND FINITE AUTOMATA
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
NFA is slower to process and its representation uses more memory than DFA
|
|
|
DFA is faster to process and its representation uses less memory than NFA
|
|
|
NFA is slower to process and its representation uses less memory than DFA
|
|
|
DFA is slower to process and its representation uses less memory than NFA
|
Detailed explanation-1: -Generally speaking, DFA is faster, but NFA is more compact. The NFA is proportional to the size of the regular expression. (Informal proof: each operator node in a regular expression’s syntax just adds a new node to the NFA graph.)
Detailed explanation-2: -Statement 1: Initial State of NFA is Initial State of DFA. Statement 2: The final state of DFA will be every combination of final state of NFA. Correct answer is option ‘A’.
Detailed explanation-3: -If we compare which is more powerful (in accepting strings), both are same. But what about efficiency ? DFA will be fast compared to NFA, since it has only one outgoing edge & there will be no ambiguity. But in case of NFA we have to check all possible cases & that surely takes time.
Detailed explanation-4: -A DFA is just a special case of an NFA that happens not to have any null transitions or multiple transitions on the same symbol. So DFAs are not more powerful than NFAs. For any NFA, we can construct an equivalent DFA (see below). So NFAs are not more powerful than DFAs.