I have my own version of
lex and I would like to add the complement operation. Derived from that I can then add the intersection and difference also. My version also supports the generation of NFAs (Non-deterministic Finite Automaton) and of course I try to keep the automatons as small as possible.
My question thus is: what is the most optimal known upper bound on the number of states in the NFA that accepts the complement of another NFA? Of course going through the conversion to a DFA (Deterministic Finite Automaton) and then interchanging accepting and rejecting states, gives an exponential upper bound. Are there any better known upper bounds? Preferably polynomial or even linear of course.
If no better upper bound is known, has it been shown that for some family of languages the lower bound is exponential or otherwise super polynomial?