Language described by inverting accepting states of NFA

Question

Connecting to When states that are not accepting states become accepting states in NFA, what happens?, what is the formal language described by inverting accepting states of NFA? By inverting, I mean that rejecting states become accepting states and accepting states become rejecting states.

Is there a nice expression for such a language reference to the original NFA language?

Answer 1

The answer is basically in the question you link, but to make it explicit: no, there is no "nice expression" since anything can happen.

For an example, let $L$ be any regular language; let's say it's accepted by NFA $A_L$:

^[source]

Now consider this automaton $A'_L$:

^[source]

Clearly, $A_L$ and $A'_L$ accept the same language $L$. However, the automaton obtained from flipping $A'_L$ accepts $\Sigma^*$ (since $s$ is accepting in this one).

So we see that we need further assumptions on the automata if flipping is to yield anything meaningful. For instance, if we require that for every input, either all computations are accepting or all are rejecting -- a property $A'_L$ above does not have -- then flipping yields the complement of the original language.