[8uhaal]

Ah ok, thanks. What I meant was that you could flip the states if it's a DFA. If you have an NFA then that won't work, as shown by your counterexample.

I suppose you generally accept in an NFA if there is an accepting state epsilon-reachable, so if you flip the accepting states, you could still have an accepting state epsilon-reachable, which is why this doesn't work. In an DFA, there is only one state that's (trivially) epsilon-reachable, so the construction works.

[mcyc]

While epsilon transitions often, but not always, cause this issue of not being able to complement the language by just flipping final/non-final states, it isn't always the case. For example, you can make an ambiguous NFA with no epsilon transitions by just doing epsilon removal, and then you still have the same problem but no non-trivial epsilon-reachable states!

On the other hand, you can have an unambiguous [1] NFA (for example, a DFA, but you insert some dummy epsilon transitions between a split up state) where you can just flip the final/non-final states and complement the language.

So, in the end, complementing languages described by NFAs without determinizing them first is a bit of a tricky problem.

[1]: https://en.wikipedia.org/wiki/Unambiguous_finite_automaton --- a superset of DFAs, but they can have epsilon transitions

[8uhaal]

Oh, interesting! Thanks for the pointer!

But you can't always complement the language easily for an UFA either, right? The path to an accepting state may be unambiguous, but there could at the same time be a path to a non-accepting state, so flipping the states may keep some words in the language. And make the automaton even ambiguous.