COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
128
|
|
|
127
|
|
|
68
|
|
|
67
|
Detailed explanation-1: -Solutions for If NFA of 6 states excluding the initial state is converted into DFA, maximum possible number of states for the DFA is ? a)64b)32c)128d)127Correct answer is option āCā.
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.
Detailed explanation-3: -In NFA, when a specific input is given to the current state, the machine goes to multiple states. It can have zero, one or more than one move on a given input symbol. On the other hand, in DFA, when a specific input is given to the current state, the machine goes to only one state.
Detailed explanation-4: -As per the definition of DFA, so as NFA it can have only one initial state.
Detailed explanation-5: -ā“ Minimum number of states required for DFA = 3.