GATE CS 2018 Q.16 (CS Q.6): Regular Expressions, Finite Automata and Regular Languages

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?

$k \ge 2^n$

$k \ge n$

$k \le n^2$

$k \le 2^n$

Official answer and solution

Official answer: D
From: Official GATE 2018 answer key

Solution

Apply the powerset construction to determine the maximum upper bound on states in an equivalent DFA.

An NFA $N$ with $n$ states can be converted to an equivalent DFA using the subset construction (powerset construction). In this construction, each state of the DFA corresponds to a subset of states of $N$ .

Since a set of $n$ elements has exactly $2^n$ subsets, the constructed DFA has at most $2^n$ states.

State minimization of a DFA either maintains or decreases the total number of states. Hence, the minimal equivalent DFA has $k \le 2^n$ states.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2018 Computer Science and Information Technology (CS)
Question: 16 of 65, printed as CS Q.6
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source