# 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 end-state with the RE of the $L_{NFA}$ written on the bow between.

So I think the GNFA can be smaller (less states) because you can make choices. For instance a bow from state 1 to state 2 could contain: $ab | a$ which in a DFA would require more states.

So my question is basically: Am I right about this? Can you there exist a smaller NFA to a minimal DFA?

• And see also cs.stackexchange.com/questions/6063/… which has an explicit construction for a slightly weaker bound. – Gilles 'SO- stop being evil' Aug 29 '16 at 12:07
• I don't understand what GNFA have to do here. As you have a regular expression on the arcs, any language could be represented with a 2 state GNFA. But this has nothing to do with NFA vs DFA size. For this later case, see the duplicates. – dodecaplex Aug 29 '16 at 14:27