COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
The construction time for DFA from an equivalent NFA (m number of node)is
|
|
O(m2)
|
|
|
O(2m)
|
|
|
O(m)
|
|
|
O(log m)
|
Explanation:
Detailed explanation-1: -For DFA D = (Q, , D, q0, F), define an “equivalent” NFA N = (Q, , N, q0, F) that has the exact same set of states, initial state and final states. Only difference is in the transition function. N (q, a) = D(q, a) for a ∈ and N (q, ) = ∅ for all q ∈ Q.
Detailed explanation-2: -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. N = (Q, , , q0, F ) defined as: 1. Q = P(Q)-we have a state in Q to represent each possible subset of states in Q.
Detailed explanation-3: -yes it may be NFA have more then number of states from minimized DFA.
There is 1 question to complete.