3
$\begingroup$

It is well known that deterministic Büchi automata (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?

$\endgroup$
10
$\begingroup$

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.

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