Let $L_1=\{Q,\Sigma,q_0,\delta,Q\}$ be a DFA that accepts a language $L$ and where all the states are also final states. If we want a DFA that accepts the complement of $L$, we swap its accepting states with its non-accepting states, that is $\overline{L_1}=\{Q,\Sigma,q_0,\delta,Q-Q\}$. In this case we have a DFA without final states. Is this still a DFA? Is it regular?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ What is a DFA for you? Is $\delta$ a total function? $\endgroup$– Yuval FilmusApr 16, 2020 at 15:24
-
$\begingroup$ The definition of a DFA just requires the set of final states to be a subset of the set of states. We don't require anything else. In particular, a DFA is allowed to have no accepting state, or no non-accepting state. A DFA without accepting states accepts the empty language, hence this language is regular (since a language is regular iff it is accepted by some DFA). $\endgroup$– Yuval FilmusApr 16, 2020 at 15:26
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
It's common to write DFAs which don't have transitions on every symbol. These are called "incomplete" DFAs, and there is really nothing wrong with them as long as it is understood that they are incomplete. But they don't satisfy all of the requirements of algorithms which require complete DFAs, and the complement algorithm you are using is one of those. (There are many other such algorithms. For example, Hopcroft's state minimization algorithm doesn't work on incomplete automata, at least without some adjustment.)
If the DFA you are referring to is complete and has no non-accepting states, then it must be the case that it recognises $\Sigma^*$ so that its complement is the empty set. But I have a hunch that's not the case.
You can always convert an incomplete DFA into a complete DFA by adding a single non-accepting state with a looping transition on every symbol. (This is usually called the "sink" state, because there is no way out.) Then for every other state which has no transition on one or more symbols, you add all the missing transitions with the sink state as a destination. Since the sink state is non-accepting and non-escapable, this operation does not in any way alter the language recognised by the DFA.
Once you've done that, it is (probably) no longer the case that every state in the DFA is accepting; there is now one non-accepting state. And the complement algorithm will make that non-accepting state accepting, and all the other states non-accepting, which will produce the complement of the language.
$\begingroup$
$\endgroup$
If I understood it correctly, then $L$ contains every possible string, because no matter what the input is, $L_1$ will terminate on a final state.
Since $L_1$ accepts every possible string, its complement should accept no strings, hence the empty language.
