edited by
10,267 views
24 votes
24 votes

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?

  1. $k \geq 2^n$
  2. $k \geq n$
  3. $k \leq n^2$
  4. $k \leq 2^n$
edited by

2 Answers

Best answer
36 votes
36 votes
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}$.
selected by
7 votes
7 votes
If NFA having $n$ states then equivalent DFA can have atmost $2^n$ states.
edited by
Answer:

Related questions

32 votes
32 votes
6 answers
1
41 votes
41 votes
9 answers
3
23 votes
23 votes
6 answers
4
gatecse asked Feb 14, 2018
10,122 views
Consider a matrix $A= uv^T$ where $u=\begin{pmatrix}1 \\ 2 \end{pmatrix} , v = \begin{pmatrix}1 \\1 \end{pmatrix}$. Note that $v^T$ denotes the transpose of $v$. The larg...