COMPUTER SCIENCE AND ENGINEERING
COMPILER DESIGN
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
dfa
|
|
|
nfa
|
|
|
cant say
|
|
|
both have same
|
Detailed explanation-1: -As a result, the dfa may have exponentially more states than the nfa.
Detailed explanation-2: -A state in a DFA will be a subset of the set of states of the equivalent NFA. So, the maximum number of states in the equivalent DFA of an NFA, will be 2n, where n is the number of states in NFA, as a set with n items has maximum 2n subsets. GATE CS Admit Card Out on 9th January 2023.
Detailed explanation-3: -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.
Detailed explanation-4: -NFA usually requires significantly less states than DFA to recognize the same language. NFAs in one letter input alphabet are more restricted and the gap between NFAs and DFAs decreases, because the power of NFA is in its ability to reach many subsets of its state set.
Detailed explanation-5: -(i) NFA is more powerful than DFA but DFA is more efficient than NFA. (ii) NFA will respond for only valid inputs and no need to respond for invalid inputs. (iii) There is no concept of dead states and complement in NFA. (iv) NFA is a parallel computing system where we can run multiple threads concurrently.