GATE 2018 CS Q.6: solution and answer

GATE 2018 · CSQ.6 · 1 mark · MCQ

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}$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The minimal DFA never needs more than $2^{n}$ states, so (D) $k \leq 2^{n}$ is the option that is necessarily true.

Official answer: DSource: Official answer key, GATE 2018 CS (IIT Guwahati)

Subset construction: every state of the DFA built from an $n$ -state NFA is a subset of the NFA's states, so it is one of at most $2^{n}$ subsets (including $\emptyset$ ).
So the subset-construction DFA has at most $2^{n}$ states. A minimal DFA for the same language is never larger than any equivalent DFA, so $k \leq 2^{n}$ always holds. This is option (D).
(A) $k \geq 2^{n}$ is not necessary: a one-state NFA ( $n = 1$ ) for $a^{*}$ has a minimal DFA with $k = 1 < 2^{1} = 2$ .
(B) $k \geq n$ is not necessary: a 3-state NFA ( $n = 3$ ) accepting $Σ^{*}$ has a minimal DFA with $k = 1 < 3$ .
(C) $k \leq n^{2}$ is not necessary: the language $(a + b)^{*} a (a + b)^{m - 1}$ (the $m$ -th symbol from the end is $a$ ) has an NFA with $n = m + 1$ states, but every DFA for it needs at least $2^{m}$ states. For $m = 6$ this gives $n = 7$ and $k = 64 > 49 = n^{2}$ .
Only (D) holds for every NFA.

KEY IDEA

Subset construction turns an $n$ -state NFA into a DFA with at most $2^{n}$ states, and minimisation can only shrink it. This gives an upper bound only.

WATCH OUT FOR

Choosing (A) because the exponential blow-up is famous. The $2^{n}$ figure is only a worst case, and many NFAs give a far smaller minimal DFA, even one with fewer states than the NFA.

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 18 Finite automata questions, with notes

GATE 2018 CS Q.6: solution and answer

Answer and solution

More Finite automata questions