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?

  • $\begingroup$ And see also cs.stackexchange.com/questions/6063/… which has an explicit construction for a slightly weaker bound. $\endgroup$ Aug 29 '16 at 12:07
  • $\begingroup$ 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. $\endgroup$
    – dodecaplex
    Aug 29 '16 at 14:27