Languages acceptable with just a single final state

Question

For a given regular language $L$ we can always find a corresponding automaton with exactly one initial state, this is quite a common result and in most textbooks even non-deterministic automata are just allowed to have a single start state.

Now I am curious under what conditions is a single final state sufficient. Of course, sometimes a single final state is not enough (even for non-deterministic automata), for example for the language $L = \{a, bb\}$ or $L = a \cup bb^{\ast}$ (of course under the assumption that $\varepsilon$-transition are not allowed).

I guess if we allow multiple initial states in non-deterministic automata, then we can always find a non-deterministic automata with a single final state (it might have multiple start states). For a proof, if $L$ is regular, then let $\mathcal A$ be an accepting automaton for $L^R$ (i.e. the mirrored language) with a single initial state $q_0$. Then reverse all transitions and declare $q_0$ to be its single final state, and all original final states as initial states, and we have an automaton for $(L^R)^R = L$ which has just a single final state.

So is this observation correct, or are there automata for which we always need more than one final state, even if we allow multiple start states. And also could the languages which could be accepted with just a single final state (in the deterministic, and in the non-deterministic with a single initial state) somehow characterised?

Also note that $L = X^{\ast}0X$ for $X = \{0,1\}$ could not be accepted by a DEA with a single final state, but by an NEA with a single final state and a single initial state.

EDIT: A straightforward characterisation for the deterministic case, as the number of nerode right-congruence classes whose union is $L$ is an upper bound for the number of final states (as they could not be further merged), we have that $L$ could be accepted by such an automaton iff it is itself an equivalence class. This also shows that by adding final states we could not gain anything in the sense that the automaton gets smaller.

Answer 1

According to Eilenberg [1, Chap. IV, Prop. 1.1], the following result holds:

Proposition. For any nonempty subset $L$ of $A^*$, the following conditions are equivalent:

1. for all $u, v \in L$, $u^{-1}L = v^{-1}L$,
2. the minimal automaton of $L$ has a single final state,
3. $L$ is recognized by a deterministic automaton with a single final state that is accessible.

[1] S. Eilenberg, Automata, Languages and Machines, Volume A, Academic Press (1974)

See also my answer to the related question (N)DFA with same initial/accepting state(s) on cstheory.

Answer 2

You can always make a non-deterministic automaton with a single accepting state for any regular language (even without $\varepsilon$-transitions) -- unless the language contains the empty string and is not closed under concatenation. Just take an automaton without this restriction and create a new accepting state, and then for each transtion into a state that used to accept, supplement it with a transition on the same symbol that goes to the central accepting state. (There will be no transitions out of the accepting state).

This is not always case for deterministic automata, but your examples are not quite right. You can make a DFA with a single accepting state for $a\cup bb$, but not for $a\cup bb^*$.

You can do with a single accepting state unless there are words $u$, $v$, and $w$ such that $u$, $v$ and $vw$ are in the language but $uw$ isn't.

In the case of $a\cup bb^*$, you could take $u=a$, $v=w=b$.

Reversing a deterministic automaton is not as simple as you make it out to be, because a DFS can have several transitions on the same symbol into a given state, and just reversing everything will give you a non-deterministic automaton instead.