<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2016-06-29T22:23:34.687Z
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.
J.-E. Pin
CC BY-SA 3.0
2016-06-30T03:28:16.060Z
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.
mikero
CC BY-SA 3.0
2016-06-30T12:19:44.370Z
@J.-E.Pin: Yes, thank you, I updated my answer.
Huck Bennett
CC BY-SA 3.0
2013-07-07T07:54:49.610Z
2016-06-30T12:19:13.900Z
2016-06-30T12:19:13.900Z
Huck Bennett
<p>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. </p>

<p>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.</p>

<blockquote>
  <p><a href="http://dl.acm.org/citation.cfm?id=322334">Inference of Reversible Languages</a>, Dana Angluin, Journal of the ACM, 1982</p>
</blockquote>

CC BY-SA 3.0
2013-07-07T00:56:22.883Z
2013-07-07T00:56:22.883Z
Vijay D
<p>You can refer to Semi-flower automata, as their paper puts it: "A semi-ﬂower automaton (SFA) is a trim automaton with a unique initial state that is equal to a unique ﬁnal
state in which all the cycles shall pass through the initial-ﬁnal state". Refer to "THE HOLONOMY DECOMPOSITION OF CIRCULAR SEMI-FLOWER AUTOMATA" -Shubh Narayan Singh, K. V. Krishna.</p>

CC BY-SA 3.0
2013-07-16T07:47:40.817Z
2013-07-16T07:47:40.817Z
Viresh
<p>This question is solved for deterministic automata and for unambiguous automata in the book [1]</p>

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

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

<blockquote>
  <p><strong>Proposition</strong>. Let $L$ be a regular subset of $A^*$. The following conditions are equivalent:</p>
  
  <ol>
  <li>$L$ is a right unitary submonoid,</li>
  <li>$L = P^*$ for some prefix code $P$,</li>
  <li>The minimal automaton of $L$ has a unique final state, namely the initial state.</li>
  <li>There exists a deterministic automaton recognizing $L$ having the initial state as unique final state.</li>
  </ol>
</blockquote>

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

<blockquote>
  <p><strong>Proposition</strong>. Let $L$ be a regular subset of $A^*$. The following conditions are equivalent:</p>
  
  <ol>
  <li>$L$ is a free submonoid of $A^*$,</li>
  <li>$L = C^*$ for some code $C$,</li>
  <li>There exists an unambiguous automaton recognizing $L$ having the initial state as unique final state.</li>
  </ol>
</blockquote>

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

CC BY-SA 3.0
2016-06-30T02:51:45.020Z
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).
gdmclellan
CC BY-SA 3.0
2016-06-30T10:07:11.530Z
@gdmclellan You are perfectly right. The precise reference is Chap. IV, Proposition 3.2.
J.-E. Pin
CC BY-SA 3.0
2016-06-30T17:17:14.683Z
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?
StefanH
CC BY-SA 3.0
2016-06-29T22:25:50.860Z
2016-06-29T22:25:50.860Z
J.-E. Pin
<p>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?</p>

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

CC BY-SA 3.0
2013-07-05T08:19:59.540Z
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.
Huck Bennett
CC BY-SA 3.0
2013-07-06T10:47:23.880Z
Ah, of course.  Thanks!  If you'd like to post this comment as an answer, I will accept it and close the question.
Noam Zeilberger
<fl.formal-languages><automata-theory><algebra><regular-language>
(N)DFA with same initial/accepting state(s)
Noam Zeilberger
# (N)DFA with same initial/accepting state(s)

(Asked by: username_0 on 2013-07-05)

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.

**Tags:** fl.formal-languages, automata-theory, algebra, regular-language
> **Comments:**
> **username_1**: 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.  
> **username_0**: Ah, of course.  Thanks!  If you'd like to post this comment as an answer, I will accept it and close the question.  

---

## 4 answers

### Answer by username_2 on 2016-06-29. Score: 8 | Accepted answer

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^\*$.

> **Comments:**
> **username_6**: 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).  
> **username_2**: @gdmclellan You are perfectly right. The precise reference is Chap. IV, Proposition 3.2.  
> **username_7**: 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?  

---

### Answer by username_1 on 2013-07-07. Score: 14

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.

> **Comments:**
> **username_2**: 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.  
> **username_3**: 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.  
> **username_1**: @J.-E.Pin: Yes, thank you, I updated my answer.  

---

### Answer by username_4 on 2013-07-07. Score: 10

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](http://dl.acm.org/citation.cfm?id=322334), Dana Angluin, Journal of the ACM, 1982


---

### Answer by username_5 on 2013-07-16. Score: 1

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


---

