COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
Statement 1 is true and Statement 2 is true
|
|
|
Statement 1 is true and Statement 2 is false
|
|
|
Statement 1 can be true and Statement 2 is true
|
|
|
Statement 1 is false and Statement 2 is also false
|
Detailed explanation-1: -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-2: -Every NFA is not DFA, but each NFA can be translated into DFA. NFA is defined in the same way as DFA but with the following two exceptions, it contains multiple next states, and it contains transition.
Detailed explanation-3: -The correct answer is option 4. Option i: For every NFA with an arbitrary number of final states, there is an equivalent NFA with only one final state. True, Every NFA with more than one final state can be converted into an NFA with a single final state.
Detailed explanation-4: -For every n ≥ 1 there exists an NFA M over a binary alphabet with n states, each of which is both initial and final, such that the minimal DFA accepting L(M) has 2n states. Proof. For n = 1 we take the automaton with a single state which is both initial and final, with a self-loop on only one of the two letters.
Detailed explanation-5: -In particular, every DFA is also an NFA. Sometimes the term NFA is used in a narrower sense, referring to an NFA that is not a DFA, but not in this article. Using the subset construction algorithm, each NFA can be translated to an equivalent DFA; i.e., a DFA recognizing the same formal language.