COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
Yes
|
|
|
No
|
|
|
Either A or B
|
|
|
None of the above
|
Detailed explanation-1: -The set of all strings accepted by an NFA is the language the NFA accepts. This language is a regular language. For every NFA a deterministic finite automaton (DFA) can be found that accepts the same language.
Detailed explanation-2: -A language L is recognized by a DFA if and only if there is an NFA N such that L(N) = L. In other words: For any DFA D, there is an NFA N such that L(N) = L(D), and • For any NFA N, there is a DFA D such that L(D) = L(N).
Detailed explanation-3: -The language accepted by an NFA < Q, , q0, , A > is the set of strings that are accepted by the NFA. Some of the strings accepted by the NFA given above are, a, ab, aaa, abbbb etc. and the language it accepts is a*( ab + a + ba )(bb)* . for NFA has properties similar to that for DFA.
Detailed explanation-4: -Every DFA has an equivalent NFA. (Proof by construction-trivial.) Given N = (Q, , , q0, F), and NFA recognizing some language A. We prove that every NFA has an equivalent DFA by showing how to construct a DFA N from N that recognizes the same language A.