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?
Optimal upper bound on the number of states in the complement of an NFA
finite automata
In the paper State Complexity of Concatenation andComplementation of Regular Languages by Jirsek, Jirskov, and Szabari (LNCS Volume 3317, 2005, doi 10.1007/978-3-540-30500-2_17) very precise bounds for complexities for complement on non-deterministic automata are obtained. We do not need full details, but the authors cite an earlier report by one of them, stating:Theorem 2. For any positive integer $n$, there exists a binary NFA $M$ of$n$ states such that any NFA for the complement of the language $L(M)$ needs atleast $2^n$ states.So it seems there is no better bound for complementation than via deterministic automata. At least in general. 