<p>This question generated a lot of literature in the 80's, partly due to a bad approach to the problem. This is a rather long story that I will try to summarize in this answer. </p>

<p><strong>1. The case of finite words</strong></p>

<p>One can find two definitions of a minimal DFA in the literature. 
The first one is to define the minimal DFA of a regular language as the complete DFA with the minimum number of states accepting the language.
The second one is longer to define but is mathematically more appealing than the first one and it gives stronger properties.</p>

<p>Let us recall that a DFA $(Q, A, \cdot, i, F)$ is <em>accessible</em> if for all $q \in Q$, there is a word $u \in A^*$ such that $i \cdot u = q$. It is <em>complete</em> if $q \cdot a$ is defined for all $q \in Q$ and $a \in A$.</p>

<p>Let ${\cal A}_1 = (Q_1, A, \cdot, i_1, F_1)$ and ${\cal A}_2 = (Q_2, A,
\cdot, i_2, F_2)$ be two complete, accessible DFAs. A morphism from $\mathcal{A}_1$ to $\mathcal{A}_2$  is a function $\varphi:Q_1 \to Q_2$ such that </p>

<ol>
<li>$\varphi(i_1) = i_2$,</li>
<li>$\varphi^{-1}(F_2) = F_1$,</li>
<li>for all $q \in Q_1$ and $a \in A$, $\varphi(q)\cdot a=\varphi(q\cdot a)$.</li>
</ol>

<p>One can show that these conditions imply that $\varphi$ is necessarily surjective (and thus $|Q_2| \leqslant |Q_1|$). Furthermore, there is at most one morphism from ${\cal A}_1$ to ${\cal A}_2$ and if this morphism exists, then ${\cal A}_1$ and ${\cal A}_2$ recognize the same language. Now, one can show that for every language $L$, there is a unique complete accessible DFA ${\cal A}_L$ accepting $L$ and such that, for every complete accessible DFA $\cal A$ accepting $L$, there is a morphism from $\cal A$ onto 
${\cal A}_L$. This automaton is called the <em>minimal DFA</em> of $L$. Note again that since
the number of states in ${\cal A}_L$ is smaller than the number of states in $\cal A$, ${\cal A}_L$ is also minimal in the first sense.</p>

<p>It is worth mentioning that there is also a suitable algebraic definition for <em>incomplete</em> DFAs. See [Eilenberg, <em>Automata, Languages and Machines</em>, vol. A, Academic Press, 1974] for more details.</p>

<p><strong>2. Back to infinite words</strong> </p>

<p>Extending the first definition does not work, as shown by Shaull in his answer. And unfortunately one can also show that the universal property of the second definition does not extend to infinite words, except in a few particular cases. </p>

<p>Is it the end of the story? Wait a second, there is another minimal object that accepts regular languages...</p>

<p><strong>3. The syntactic approach</strong></p>

<p>Let us first return again to finite words. Recall that a language $L$ of $A^*$ is
<em>recognized by a monoid</em> $M$ if there is a surjective monoid morphism
$f:A^* \to M$ and a subset $P$ of $M$ such that $f^{-1}(P) = L$. Again, there exists a monoid $M(L)$, called the <em>syntactic monoid</em> of $L$, which recognizes $L$ and is a quotient of all monoids recognizing $L$. This syntactic monoid can be defined directly as the quotient of $A^*$ by the <em>syntactic congruence</em> $\sim_L$ of $L$, defined as follows:
$$
  \text{$u \sim_L v$ if and only if, for all $x, y \in A^*$, $xuy \in L \iff xvy \in L$} 
$$
The good news is that this time, this approach has been extended to infinite words, but it took a long time to discover the appropriate notions. 
First, the suitable notion of a syntactic congruence was found by A. Arnold (A syntactic congruence for rational $\omega$-languages, <em>Theoret. Comput. Sci.</em> <strong>39</strong>,2-3 (1985), 333–335).
Extending syntactic monoids to the setting of infinite words required a more sophisticated type of algebras, called nowadays <em>Wilke algebras</em> in honor of T. Wilke, who was the first to define them (T. Wilke, An algebraic theory for regular languages of finite and infinite words, <em>Int. J. Alg. Comput.</em> <strong>3</strong> (1993), 447–489). More details
can be found in my book <em>Infinite words</em> coauthored with D. Perrin.</p>

<p><strong>4. Conclusion</strong></p>

<p>Thus there is a mathematically sound notion of a minimal object accepting a given regular $\omega$-language, but it does not rely on automata.
This is actually a rather generic fact: automata are a very powerful algorithmic tool, but they are not always sufficient to treat mathematical questions on languages.</p>

CC BY-SA 3.0
2015-01-04T13:16:09.243Z
2015-01-04T15:47:30.103Z
2015-01-04T15:47:30.103Z
J.-E. Pin
<p>In general, $\omega$-regular languages may not have a unique minimal DBW. For example, the language "infinitely many a's and infinitely many b's" has two 3-state DBWs (in the picture replace $\neg a$ by $b$):
<img src="https://i.sstatic.net/dC6Id.png" alt="Two minimal DBWs for the same language"></p>

<p>As you can see, they are not topologically equivalent.</p>

<p>Hence, the minimization problem is harder than the finite case, and in fact, it is <a href="http://arxiv.org/pdf/1007.1333.pdf" rel="noreferrer">NP-complete</a>.</p>

CC BY-SA 3.0
2014-12-26T23:23:34.530Z
I found three 3-state deterministic Büchi-Automata, two are structurally very similar (they just differ by the labels on their transitions), but would you mind nonetheless to give your machines, just for comparison :) Thanks for the article!
StefanH
CC BY-SA 3.0
2014-12-27T07:36:20.043Z
@Stefan - added the example.
Shaull
CC BY-SA 3.0
2014-12-27T11:31:54.860Z
The left one I have too, but I also have a different one, I posted it as an edit in my question.
StefanH
CC BY-SA 3.0
2014-12-27T11:36:36.980Z
The automaton you added is incorrect - it doesn't accept the word $(bab)^\omega=babbabbabbab...$
Shaull
CC BY-SA 3.0
2017-12-05T10:33:17.303Z
@BaderAbuRadi - good question. In the reduction (in this [paper by Sven Schewe](https://arxiv.org/pdf/1007.1333.pdf)) the alphabet is not constant. It may be the case that it can be encoded in binary, but this requires going into the details.
As for bounding the number of equivalent states - you can definitely get by with only two sinks - one accepting and one rejecting. But other states will be more problematic...
Shaull
CC BY-SA 3.0
2014-12-26T22:44:38.503Z
2014-12-27T07:35:51.040Z
2014-12-27T07:35:51.040Z
Shaull
<p>What is the standard approach on minimizing Büchi-Automata (or also Müller-Automata)? Transfering the usual technique from finite words, i.e. setting two states to be equal if the words "running out" of the states which are accepted are the same, will not work. For example consider the Büchi-Automoton accepting all words with an infinite number of a's consisting of two states,  a initial and a final state, and the final state is entered each time an a is read, and the initial state is entered each time a different symbol is read. Both states are considered equal by the above defintion, but collapsing them yields an automata consisting of a single state, and thereby accepting every words.</p>

<fl.formal-languages><automata-theory><omega-language>
Minimizing Automata accepting $\omega$-words (i.e. infinite words)
StefanH
# Minimizing Automata accepting $\omega$-words (i.e. infinite words)

(Asked by: username_0 on 2014-12-26)

What is the standard approach on minimizing Büchi-Automata (or also Müller-Automata)? Transfering the usual technique from finite words, i.e. setting two states to be equal if the words "running out" of the states which are accepted are the same, will not work. For example consider the Büchi-Automoton accepting all words with an infinite number of a's consisting of two states, a initial and a final state, and the final state is entered each time an a is read, and the initial state is entered each time a different symbol is read. Both states are considered equal by the above defintion, but collapsing them yields an automata consisting of a single state, and thereby accepting every words.

**Tags:** fl.formal-languages, automata-theory, omega-language

---

## 2 answers

### Answer by username_2 on 2014-12-26. Score: 11 | Accepted answer

In general, $\omega$-regular languages may not have a unique minimal DBW. For example, the language "infinitely many a's and infinitely many b's" has two 3-state DBWs (in the picture replace $\neg a$ by $b$):
![Two minimal DBWs for the same language](https://i.sstatic.net/dC6Id.png)

As you can see, they are not topologically equivalent.

Hence, the minimization problem is harder than the finite case, and in fact, it is [NP-complete](http://arxiv.org/pdf/1007.1333.pdf).

> **Comments:**
> **username_0**: I found three 3-state deterministic Büchi-Automata, two are structurally very similar (they just differ by the labels on their transitions), but would you mind nonetheless to give your machines, just for comparison :) Thanks for the article!  
> **username_2**: @Stefan - added the example.  
> **username_0**: The left one I have too, but I also have a different one, I posted it as an edit in my question.  
> **username_2**: The automaton you added is incorrect - it doesn't accept the word $(bab)^\omega=babbabbabbab...$  
> **username_2**: @BaderAbuRadi - good question. In the reduction (in this [paper by Sven Schewe](https://arxiv.org/pdf/1007.1333.pdf)) the alphabet is not constant. It may be the case that it can be encoded in binary, but this requires going into the details. As for bounding the number of equivalent states - you can definitely get by with only two sinks - one accepting and one rejecting. But other states will be more problematic...  

---

### Answer by username_1 on 2015-01-04. Score: 12

This question generated a lot of literature in the 80's, partly due to a bad approach to the problem. This is a rather long story that I will try to summarize in this answer.

**1. The case of finite words**

One can find two definitions of a minimal DFA in the literature.
The first one is to define the minimal DFA of a regular language as the complete DFA with the minimum number of states accepting the language.
The second one is longer to define but is mathematically more appealing than the first one and it gives stronger properties.

Let us recall that a DFA $(Q, A, \cdot, i, F)$ is *accessible* if for all $q \in Q$, there is a word $u \in A^\*$ such that $i \cdot u = q$. It is *complete* if $q \cdot a$ is defined for all $q \in Q$ and $a \in A$.

Let ${\cal A}\_1 = (Q\_1, A, \cdot, i\_1, F\_1)$ and ${\cal A}\_2 = (Q\_2, A,
\cdot, i\_2, F\_2)$ be two complete, accessible DFAs. A morphism from $\mathcal{A}\_1$ to $\mathcal{A}\_2$ is a function $\varphi:Q\_1 \to Q\_2$ such that

1. $\varphi(i\_1) = i\_2$,
2. $\varphi^{-1}(F\_2) = F\_1$,
3. for all $q \in Q\_1$ and $a \in A$, $\varphi(q)\cdot a=\varphi(q\cdot a)$.

One can show that these conditions imply that $\varphi$ is necessarily surjective (and thus $|Q\_2| \leqslant |Q\_1|$). Furthermore, there is at most one morphism from ${\cal A}\_1$ to ${\cal A}\_2$ and if this morphism exists, then ${\cal A}\_1$ and ${\cal A}\_2$ recognize the same language. Now, one can show that for every language $L$, there is a unique complete accessible DFA ${\cal A}\_L$ accepting $L$ and such that, for every complete accessible DFA $\cal A$ accepting $L$, there is a morphism from $\cal A$ onto
${\cal A}\_L$. This automaton is called the *minimal DFA* of $L$. Note again that since
the number of states in ${\cal A}\_L$ is smaller than the number of states in $\cal A$, ${\cal A}\_L$ is also minimal in the first sense.

It is worth mentioning that there is also a suitable algebraic definition for *incomplete* DFAs. See [Eilenberg, *Automata, Languages and Machines*, vol. A, Academic Press, 1974] for more details.

**2. Back to infinite words**

Extending the first definition does not work, as shown by Shaull in his answer. And unfortunately one can also show that the universal property of the second definition does not extend to infinite words, except in a few particular cases.

Is it the end of the story? Wait a second, there is another minimal object that accepts regular languages...

**3. The syntactic approach**

Let us first return again to finite words. Recall that a language $L$ of $A^\*$ is
*recognized by a monoid* $M$ if there is a surjective monoid morphism
$f:A^\* \to M$ and a subset $P$ of $M$ such that $f^{-1}(P) = L$. Again, there exists a monoid $M(L)$, called the *syntactic monoid* of $L$, which recognizes $L$ and is a quotient of all monoids recognizing $L$. This syntactic monoid can be defined directly as the quotient of $A^\*$ by the *syntactic congruence* $\sim\_L$ of $L$, defined as follows:
$$
\text{$u \sim\_L v$ if and only if, for all $x, y \in A^\*$, $xuy \in L \iff xvy \in L$}
$$
The good news is that this time, this approach has been extended to infinite words, but it took a long time to discover the appropriate notions.
First, the suitable notion of a syntactic congruence was found by A. Arnold (A syntactic congruence for rational $\omega$-languages, *Theoret. Comput. Sci.* **39**,2-3 (1985), 333–335).
Extending syntactic monoids to the setting of infinite words required a more sophisticated type of algebras, called nowadays *Wilke algebras* in honor of T. Wilke, who was the first to define them (T. Wilke, An algebraic theory for regular languages of finite and infinite words, *Int. J. Alg. Comput.* **3** (1993), 447–489). More details
can be found in my book *Infinite words* coauthored with D. Perrin.

**4. Conclusion**

Thus there is a mathematically sound notion of a minimal object accepting a given regular $\omega$-language, but it does not rely on automata.
This is actually a rather generic fact: automata are a very powerful algorithmic tool, but they are not always sufficient to treat mathematical questions on languages.


---

