UGC NET CSE | December 2012 | Part 2 | Question: 44

Question

Let L be set accepted by a non-deterministic finite automaton.  The number of states in non-deterministic finite automaton is $\mid Q \mid$. The maximum number of states in equivalent finite automaton that accepts L is

• A. $\mid Q \mid$
• B. $ 2 \mid Q \mid$
• C. $2^{\mid Q \mid} -1$
• D. $2^{\mid Q \mid}$

Answer 1

Conversion from NFA to DFA is done by subset construction .If a problem can be solved with n state in NFA then in worst case number of states in the resulting DFA is 2ⁿ 

Given Number of states in NFA = |Q|

then Maximum number of states in equivalent DFA =2^|Q|

Hence,Option(D)2^|Q| is the correct choice.

Answer 2

Please refer https://gateoverflow.in/699/gate2001_1-6