23k views

### Maximum number of states in minimized DFA from NFA with $n$ states [duplicate]

If an NFA with $n$ states is converted to an equivalent minimized DFA then what will be the maximum number of states in the DFA? Will it be $2^n$ or $2n$?
• 163
3k views

### Size comparison of NFA and minimal DFA [duplicate]

Except for isomorphisms, the minimal DFA of a regular language is unique. However, is it possible that an equivalent NFA has less states than the minimal DFA? If so, what is the reasoning behind this? ...
44 views

### Can there exist a smaller NFA then a minimal DFA [duplicate]

So every NFA can be transformed to a DFA and every DFA can be transformed to a minimal DFA. But every NFA can also be transformed to a GNFA (generalized NFA) with 2 states. This is just the start and ...
40 views

### NFA -> DFA powerset construction worst case [duplicate]

I am wondering what generic example there is so that an NFA with n states results into a DFA with $2^n$ states after the conversion by the subset construction. I know there is the example by Hopcroft ...
• 155
1 vote
20 views

• 156