edited by
10,691 views
30 votes
30 votes

Let $N$ be an NFA with $n$ states and let $M$ be the minimized DFA with m states recogniz­ing the same language. Which of the following in NECESSARILY true?

  1. $m \leq 2^n$
  2. $n \leq m$
  3. $M$ has one accept state
  4. $m = 2^n$
edited by

5 Answers

Best answer
42 votes
42 votes

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 $2^n$, where $n$ is the number of states in NFA, as a set with $n$ items has maximum $2^n$ subsets. 

So, answer here is (A).

edited by
12 votes
12 votes
A) Given an nfa with n states, there could be 2^n states in its equivalent dfa in the worst case (each of its states being a unique combination of n states of the nfa). Hint: Try to remember the conversion of an nfa into dfa.

B) Take for instance, an nfa for L = 0* which requires only one state but could have many more with epsilon transitions. It could be minimised into a dfa with only two states. So, n can be greater than m.

C) A dfa can have more than one final state.

D) See B.

So, answer is A.
5 votes
5 votes
Option a is always true...you can try with some examples you will never find an instance where it violates option a
Answer:

Related questions

56 votes
56 votes
6 answers
1
Ishrat Jahan asked Oct 28, 2014
12,407 views
Consider the following two finite automata. $M_1$ accepts $L_1$ and $M_2$ accepts $L_2$.$M_1$$M_2$ Which one of the following is TRUE?$L_1 = L_2$$L_1 \subset L_2$$L_1 \ca...
44 votes
44 votes
7 answers
4
Ishrat Jahan asked Oct 28, 2014
14,806 views
Consider a CFG with the following productions.$S \to AA \mid B$$A \to 0A \mid A0 \mid 1$$B \to 0B00 \mid 1$$S$ is the start symbol, $A$ and $B$ are non-terminals and 0 an...