GATE CSE 1987 | Question: 2j

Question

State whether the following statements are TRUE or FALSE:

A minimal DFA that is equivalent to an NDFA with $n$ nodes has always $2^{n}$ states.

Comments

Here, Nodes and States are same or not?

---

Yes

---

what is node here ?

Answer 1

No a minimal DFA that is equiavlent to an NDFA with $n$ nodes has always $2^n$ states.

Correct statement is A minimal DFA that is equivalent to an NDFA with $n$ nodes has atmost  $2^n$ states.

Example :

Comments

2^n , excluding the dead state

---

Is there any example that satisfies NDFA with n states → DFA with 2^n states

?

---

@mrinmoyh This includes the dead state.The subset would have ∅ state in the corresponding DFA which would become the Dead State.

Watch this from 38:33

https://www.youtube.com/watch?v=EPgZlAn4EC0&list=PLTke5lHMAdSNmi57H0DOTzClHPK6UwSTN&index=2

Answer 2

false.
it is just upperbound on number of states obtained after coverting NFA to DFA

Answer 3

False, the minimal DFA can have states in range of n<= states<=2^n.In worst case it have 2^n states and in best case it have n states.

Comments

In the best case, Minimal $DFA$ can have just $1$ state.