13
$\begingroup$

What is known about the class of languages recognized by finite automata having the same initial and accepting state? This is a proper subset of the regular languages (since every such language contains the empty string), but how weak is it? Is there a simple algebraic characterization?

Ditto for languages recognized by non-deterministic automata having the same set of initial and accepting states.

$\endgroup$
  • 13
    $\begingroup$ Assuming you mean that the initial state must be the unique accepting state, finite automata having this structure correspond to languages of regular expressions of the form $r^*$, where $r$ is some regular expression. $\endgroup$ – Huck Bennett Jul 5 '13 at 8:19
  • $\begingroup$ Ah, of course. Thanks! If you'd like to post this comment as an answer, I will accept it and close the question. $\endgroup$ – Noam Zeilberger Jul 6 '13 at 10:47
8
$\begingroup$

This question is solved for deterministic automata and for unambiguous automata in the book [1]

[1] J. Berstel, D. Perrin, C, Reutenauer, Codes and automata, Vol. 129 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, 2009.

In the case of deterministic automata, the characterization is given in Proposition 3.2.5. Recall that a submonoid $M$ of $A^*$ is right unitary if, for all $u, v \in M$, $u, uv \in M$ implies $v \in M$.

Proposition. Let $L$ be a regular subset of $A^*$. The following conditions are equivalent:

  1. $L$ is a right unitary submonoid,
  2. $L = P^*$ for some prefix code $P$,
  3. The minimal automaton of $L$ has a unique final state, namely the initial state.
  4. There exists a deterministic automaton recognizing $L$ having the initial state as unique final state.

For unambiguous automata, the characterization follows from Theorem 4.2.2 and can be stated as follows:

Proposition. Let $L$ be a regular subset of $A^*$. The following conditions are equivalent:

  1. $L$ is a free submonoid of $A^*$,
  2. $L = C^*$ for some code $C$,
  3. There exists an unambiguous automaton recognizing $L$ having the initial state as unique final state.

Finally, for nondeterministic automata, the characterization is simply that $L$ is a submonoid of $A^*$.

$\endgroup$
  • 1
    $\begingroup$ Might be worth looking at Eilenberg's unitary-prefix monomial decomposition of regular (rational in his terminology) languages. I don't have a copy of the book with me, but it's somewhere within the earlier sections of Automata, Languages and Machines, Volume A (1974). $\endgroup$ – gdmclellan Jun 30 '16 at 2:51
  • 1
    $\begingroup$ @gdmclellan You are perfectly right. The precise reference is Chap. IV, Proposition 3.2. $\endgroup$ – J.-E. Pin Jun 30 '16 at 10:07
  • $\begingroup$ In both Propositions, could we add that $P$ and $C$ are regular? I.e. $L = P^*$ for some prefix code $P$ where $P$ could be choosen to be regular? $\endgroup$ – StefanH Jun 30 '16 at 17:17
14
$\begingroup$

Finite automata in which the initial state is also the unique accepting state have the form $r^∗$, where $r$ is some regular expression. However, as J.-E. Pin points out below, the converse is not true: there are languages of the form $r^*$ which are not accepted by a DFA with a unique accepting state.

Intuitively, given a sequence of states $q_0, \ldots, q_n$ such that $q_0 = q_n$ either $n = 0$ or the underlying state diagram must have a cycle involving $q_0$. The latter case is captured algebraically by the Kleene star.

$\endgroup$
  • 2
    $\begingroup$ The languages accepted by an automaton in which the initial state is also the unique accepting state are certainly of the form $r^*$. However, this condition does not characterize the languages accepted by such a DFA. For instance, any DFA accepting the language $(a, ab)^*$ has at least 2 final states. $\endgroup$ – J.-E. Pin Jun 29 '16 at 22:23
  • 2
    $\begingroup$ I think the correct characterization is: $L$ is accepted by a minimal DFA whose start state is the only accept state, if and only if $L$ is of the form $\alpha^*$ where $\alpha$ is prefix-free. I remember finding this in an MS/PhD thesis from the 70s, but can't find the reference. Anyway, it is not too hard to prove. $\endgroup$ – mikero Jun 30 '16 at 3:28
  • $\begingroup$ @J.-E.Pin: Yes, thank you, I updated my answer. $\endgroup$ – Huck Bennett Jun 30 '16 at 12:19
10
$\begingroup$

An important subclass of this family is a sub-class of 0-reversible languages. A language is 0-reversible if the reversal of the minimal DFA for the language is also deterministic. The reversing operation is defined as swapping initial and final states, and inverting the edge relation of the DFA. This means that a 0-reversible language can have only one accepting state. Your question is adding a further restriction that this state should be the initial state. Your restriction does not define the 0-reversible languages because minimal DFA for those languages can have distinct initial and final states.

The class of reversible languages is interesting because it was one of the first families of languages with infinitely many strings that was learnable from positive examples only. Angluin's paper provides an algebraic characterisation as well.

Inference of Reversible Languages, Dana Angluin, Journal of the ACM, 1982

$\endgroup$
1
$\begingroup$

You can refer to Semi-flower automata, as their paper puts it: "A semi-flower automaton (SFA) is a trim automaton with a unique initial state that is equal to a unique final state in which all the cycles shall pass through the initial-final state". Refer to "THE HOLONOMY DECOMPOSITION OF CIRCULAR SEMI-FLOWER AUTOMATA" -Shubh Narayan Singh, K. V. Krishna.

$\endgroup$

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.