GATE IT 2008 | Question: 6

Question

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?

• A. $m \leq 2^n$
• B. $n \leq m$
• C. $M$ has one accept state
• D. $m = 2^n$

Comments

Similar question was asked on GATE 2018:

https://gateoverflow.in/204080/gate2018-6

---

similar questions: 
https://gateoverflow.in/699/gate-cse-2001-question-1-6
https://gateoverflow.in/80594/gate-cse-1987-question-2j
https://gateoverflow.in/204080/gate-cse-2018-question-6
https://gateoverflow.in/3266/gate-it-2008-question-6

---

in NFA to DFA conversion , the resultant DFA can have atmost 2^n states because the input NFA can have atmost 2^n final states

recall the transition function delta of NFA

Q * sigma = 2^Q

Answer 1

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).

Comments

But the question is only about NFA, not epsilon NFA. So how option B is incorrect?

---

why could the reasoning for option B as …The initial NFA may have multiple “epsilon” transitions or un-reachable states, it is not strictly mentioned in the question. But, given that the equivalent DFA is in the minimized form. Therefore n>m can hold if this is the condition and thereby option B not necessarily true always. (Correct me if am wrong here.)

---

I think it should be m <= 2^n - 1 , excluding the null state. so first one should not be true, and Option B should be true as it does not say epsilon NFA it says simply NFA and  n <= m thus B should be correct.

Answer 2

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.

Comments

How option B is Incorrect ?. Question is about NFA how can we have epsilon moves in NFA. Another thing, By defination every DFA is a NFA so the no of states in a NFA cannot be more than the no. of states in Minimal DFA.

---

@pranab09

Taking a suitable example we can have what option B desires(n<=m),

However by modifying the NFA it is possibe to violate this condition, the NFA will keep changing but the MINIMAL dfa will remain same.

 

Option A takes cares of this, any modification you do in NFA 2^n will only increase.

Hence option A is true, and option B is sometimes valid.

---

Let N be the minimal NFA with n states and let M be the minimal DFA with m states recogniz­ing the same language.

If this was the question, then would option B ($n \leq m$) also always be true? 

edit: I think it's true because if it is not true that means ($n > m$) but as we already know that a DFA is also a NFA. so if the minimal NFA has more states than minimal DFA then clearly it's not minimal NFA, the minimal DFA would become the minimal NFA itself. hence, minimal NFA can have atmost as many states as the minimal DFA recogniz­ing the same language. therefore ($n \leq m$) is true in this case.

PS: for this specific case:

$\boxed{n \leq m \leq 2^n}$

if the question was this:

Let N be the minimal NFA with n states and let M be any DFA with m states recogniz­ing the same language.

then only the option B ($n \leq m$) would hold true.

So, in summary:

3 possible cases:

1) minimal NFA : $n$-states, minimal DFA : $m$-states $\Rightarrow$ $n \leq m \leq 2^n$

2) minimal NFA : $n$-states, any DFA : $m$-states $\Rightarrow$ $n \leq m$

3) any NFA : $n$-states, minimal DFA : $m$-states $\Rightarrow$ $m \leq 2^n$

---

@anujs
Well said Anuj Singh

Answer 3

Option a is always true...you can try with some examples you will never find an instance where it violates option a

Comments

What is the case when option D is correct?

Answer 4

Set of states of NFA = n
A state in a DFA is a proper suset of states of NFA of corresponding DFA.
→ No. of subsets with n elements = 2^n
→ m ≤ 2^n

Answer 5

Set of states of NFA = n
A state in a DFA is a proper suset of states of NFA of corresponding DFA.
→ No. of subsets with n elements = 2n
→ m ≤ 2n