<p>From your example, it is easy to derive a language $L$, such that neither $L$ nor its complement is recognized by a DBA.</p>

<p>Take an alphabet of four letter $\{a,b,c,d\}$, and let $L=((a+b)^* a^\omega)+(c^*d)^\omega$. It is not DBA-recognizable because of the $\{a,b\}$-part, and its complement is not because of the $\{c,d\}$-part.</p>

<p>For a less artificial example, you can for instance take on alphabet $\{a,b,c\}$ the language $L$ of words with infinitely many $b$ and finitely many $c$. Both $L$ and its complement have to check that the number of something is finite, so both are not DBA-recognizable.</p>

CC BY-SA 3.0
2013-04-25T18:57:42.967Z
2014-07-21T17:37:41.633Z
2014-07-21T17:37:41.633Z
Denis
<p>It is well known that deterministic <a href="https://en.wikipedia.org/wiki/B%C3%BCchi_automaton" rel="nofollow">Büchi automata</a> (DBA) are less expressive than non-deterministic Büchi automata (NBA), and in particular DBA are not enough to cover linear temporal logic (LTL). However, the argument often used is that DBA are not closed under complementation - that is there is a language $\mathcal D$ recognized by DBA, but $\mathcal D^c$ is not recognized by any DBA. As an example, $\mathcal D = (b^*a)^\omega$ and $\mathcal D^c = (a+b)^*a^\omega$.</p>

<p>I wonder though, whether for any $\omega$-regular language $\mathcal L$ it holds either $\mathcal L$ is recognized by some DBA, or $\mathcal L^c$ is recognized by some DBA. If not, what is an example of a language which is not recognizable by DBA and which complement is not recognizable either?</p>

<fl.formal-languages><automata-theory><regular-expressions>
Deterministic Büchi + its complement covers LTL?
SBF
# Deterministic Büchi + its complement covers LTL?

(Asked by: username_0 on 2013-04-25)

It is well known that deterministic [Büchi automata](https://en.wikipedia.org/wiki/B%C3%BCchi_automaton) (DBA) are less expressive than non-deterministic Büchi automata (NBA), and in particular DBA are not enough to cover linear temporal logic (LTL). However, the argument often used is that DBA are not closed under complementation - that is there is a language $\mathcal D$ recognized by DBA, but $\mathcal D^c$ is not recognized by any DBA. As an example, $\mathcal D = (b^\*a)^\omega$ and $\mathcal D^c = (a+b)^\*a^\omega$.

I wonder though, whether for any $\omega$-regular language $\mathcal L$ it holds either $\mathcal L$ is recognized by some DBA, or $\mathcal L^c$ is recognized by some DBA. If not, what is an example of a language which is not recognizable by DBA and which complement is not recognizable either?

**Tags:** fl.formal-languages, automata-theory, regular-expressions

---

## 1 answers

### Answer by username_1 on 2013-04-25. Score: 10 | Accepted answer

From your example, it is easy to derive a language $L$, such that neither $L$ nor its complement is recognized by a DBA.

Take an alphabet of four letter $\{a,b,c,d\}$, and let $L=((a+b)^\* a^\omega)+(c^\*d)^\omega$. It is not DBA-recognizable because of the $\{a,b\}$-part, and its complement is not because of the $\{c,d\}$-part.

For a less artificial example, you can for instance take on alphabet $\{a,b,c\}$ the language $L$ of words with infinitely many $b$ and finitely many $c$. Both $L$ and its complement have to check that the number of something is finite, so both are not DBA-recognizable.


---

