COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
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: -If a DFA is needed, algorithms exist for (a) converting the NFA to an equivalent DFA and (b) minimizing the DFA. Making gross generalizations, DFAs are faster but more complex (in terms of number of states and transitions) whereas NFAs are slower but more simple (in the same terms).
Detailed explanation-2: -In order to construct a DFA D that is equivalent to an NFA N, the DFA will “simulate” the NFA N on the given input. The computation of N on input w is completely determined by the threads that are active at each step.
Detailed explanation-3: -The maximum number of final states for a DFA can be total number of states itself and minimum would always be 1, as no DFA exits without a final state. Therefore, the solution is n+1.
Detailed explanation-4: -3 DFA cannot use Empty String transition. NFA can use Empty String transition. 4 DFA can be understood as one machine. NFA can be understood as multiple little machines computing at the same time.