4.1k views

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

edited | 4.1k views
0
if NFA has $N$ states then DFA can have  $M$ states where $1\leq M \leq 2^N$

Answer is (B) $2^N$.

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).

by Loyal (8.1k points)
edited
0

In DFA any subset of the N states

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

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
by Boss (41.2k points)

by Active (2.4k points)
Ans: B
by Loyal (7.1k points)

1
2