0
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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$:

enter image description here
[source]

Now consider this automaton $A'_L$:

enter image description here
[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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.