in Theory of Computation edited by
15,728 views
29 votes
29 votes

Given an arbitrary non-deterministic finite automaton (NFA) with $N$ states, the maximum number of states in an equivalent minimized DFA at least

  1. $N^2$
  2. $2^N$
  3. $2N$
  4. $N!$
in Theory of Computation edited by
15.7k views

1 comment

if NFA has $N$ states then DFA can have  $M$ states where $1\leq M \leq 2^N$
2
2

3 Answers

42 votes
42 votes
Best answer

Correct Option: B

In DFA any subset of the $N$ states (for $N$ element set $2^N$ subsets possible)  can become a new state and they can remain even when the DFA is minimized. So, maximum we can get $2^N$ states for the minimized DFA. (at least in question must be a typo for at most).

edited by

3 Comments

In DFA any subset of the N states

 This should be "In NFA any subset of the N states..."

0
0

Yes, it should be $atmost$.

0
0
What if they asked minimum states? will that be 1?
0
0
10 votes
10 votes
Answer is 2^N.

Example DFA-> 3rs symbol from right is x.

https://gateoverflow.in/544/gate1991_17-b

Here you have to use 2^3 symbols.

nth symbol from right is x , this DFA will have 2^n state.s

1 comment

NFA for nth symbol from right have n+1 state.

And it's equivalent DFA have 2^n state
0
0
0 votes
0 votes

Answer is B. i.e., 2N

by
Answer:

Related questions