GATE CSE 2018 | Question: 6

Question

Let $N$ be an NFA with $n$ states. Let $k$ be the number of states of a minimal DFA which is equivalent to $N$. Which one of the following is necessarily true?

• A. $k \geq 2^n$
• B. $k \geq n$
• C. $k \leq n^2$
• D. $k \leq 2^n$

Comments

Watch from 48:15

https://www.youtube.com/watch?v=I06MT0MnMco&t=0s&index=2&list=PL7HjUNIdk93ThXvz2Oa_g30Jt3Owwm4HZ

---

Same Question

https://gateoverflow.in/3266/gate2008-it-6

---

@Mk Utkarsh Thanks for the timestamp on the video.

---

https://gateoverflow.in/699/gate2001-1-6

https://gateoverflow.in/80594/gate1987-2j

Answer 1

Number of states in minimal $\text{DFA}$ - $k$ must be $\leq 2^{n}$ as each state corresponds to a subset of states of the corresponding $\text{NFA}$.

$\text{D}$ is answer.

Option $\text{B}$ is not always $\text{TRUE}$ as the $\text{NFA}$ $N$ can have epsilon moves and hence can have more number of states than the minimal $\text{DFA}$.

Comments

The minimum number of states in equivalent DFA is n and maximum is 2^n, right?

Option B could also be correct

---

It isn't mentioned that the NFA is a minimum state NFA, i.e, there may be some unnecessary states in the NFA which can be reduced. If it was mentioned that the no of states in the "minimum" NFA is "n" then "k≥n" would have been a valid option too.

Answer 2

If NFA having $n$ states then equivalent DFA can have atmost $2^n$ states.

Comments

but sir , is it not true that k will surely be greater than and equal to n

---

No. Even a DFA is also  NFA. So in that case states would be equal.

---

yeah ..thats y equal to is there