15 karma · joined April 9, 2023
Source? I find that to be a pretty bold statement.
Latest instance: ChatGPT and the hype around it.
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.
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.
That's just because of incentives. Once gasoline is 5x as expensive per mile than electric, people will charge every night. For the twice-a-year long trip, that extra gasolinr cost won't matter much, and give them the freedom they want. Without driving an extra half a ton of battery around the rest of the year.