Let n be the number of states of the automaton being converted. Which of the following statements is…
An NDFA with n states can be converted to an equivalent DFA with at most 2n states by subset construction. Each DFA state represents a subset of the NDFA state set. A…
Choose your answer
Let n be the number of states of the automaton being converted. Which of the following statements is true about the equivalence of DFA and NDFA in terms of language recognition?
Answer and explanation
Correct answer A
An NDFA with n states can be converted to an equivalent DFA with at most 2n states by subset construction. Each DFA state represents a subset of the NDFA state set. A polynomial bound does not suffice in general, and treating a DFA as an NDFA does not guarantee a reduction in states.
Practice for these exams
-
Telangana SET (TG SET)