3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @mvw For GNFA I guess $\varepsilon$-transitions are allowed, which I excluded. With $\varepsilon$-transition of course we can always find an automaton with a single final state. $\endgroup$ – StefanH Jun 29 '16 at 13:39
3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for pointing out that one example was wrong, and also for giving this easy construction for NEA's, so that we can always find NEA's with a single initial and a single terminal state. That for DEA reversing everything just give NEA's in general was clear to me. $\endgroup$ – StefanH Jun 29 '16 at 13:47
  • $\begingroup$ @Stefan: I was a little quick with the general construction -- of course the construction will not work (without $\varepsilon$-transitions) if the automaton needs to accept the empty string. (Also, out of curiosity, when you write NEA and DEA, what does the E stand for? I call them NFA and DFA). $\endgroup$ – Henning Makholm Jun 29 '16 at 13:51
  • $\begingroup$ Okay, then the special case $\varepsilon \in L$ is left. The E stands for endlich, sorry this means finite in my native language, I just naively used it here. $\endgroup$ – StefanH Jun 29 '16 at 13:57
  • 1
    $\begingroup$ @Stefan: The construction I give works if $\varepsilon\notin L$, no matter if $L$ is closed under concatenation. But if $L$ does contain $\varepsilon$ and is closed under concatenation, then there's a different construction that works, namely first ignore the $\varepsilon\in L$, and afterwards identify the starting state with the accepting one. $\endgroup$ – Henning Makholm Jun 29 '16 at 14:11
  • 1
    $\begingroup$ Clearly if $\varepsilon \in L$, then the initial state needs to be accepting, and if that is the only accepting state we have, then the language the automaton accepts is necessarily closed under concatenation. $\endgroup$ – Henning Makholm Jun 29 '16 at 14:12

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.