I want to prove that a language is not $\omega$-regular.

The language I'm working with can be defined as:

$$L = \{ a_1 \dots a_n x^\omega ~ | ~ n > 0, a_1 \dots a_n \in L^\prime \}$$

where $L^\prime$ is a specific non regular language (I omit the definition $L^\prime$ because I think it is of no help for my problem), $a_i$ are symbols in $L^\prime$ alphabet and $x$ is any symbol not in $L^\prime$ alphabet.

I'm aware of several proof techniques for proving a language is not regular (see e.g. How to prove that a language is not regular? ).

Are there similar proof techniques for proving that a language is not $\omega$-regular?

  • 1
    $\begingroup$ $\omega$-regular language is a language of infinitely long words, right? Then there is no intersection between regular and $\omega$-regular languages. No $\omega$-regular language is regular. $\endgroup$ – Karolis Juodelė Mar 29 '14 at 19:09
  • $\begingroup$ actually you are right, but I explained myself very badly ... I try to amend my question ... $\endgroup$ – FSp Mar 29 '14 at 20:16
  • $\begingroup$ @KarolisJuodelė I think the edit answers your query? $\endgroup$ – Raphael Mar 29 '14 at 20:45
  • $\begingroup$ The definition of $L'$ matters. For example, if $L'=\{a^n\mid n\in S\}$ for some undecidable set $S\subseteq\mathbb{N}$ with $1\in S$, then $L$ is just $a^+x^\omega$. $\endgroup$ – David Richerby Mar 29 '14 at 21:27
  • $\begingroup$ @DavidRicherby is it? Because the language of strings $a^+x^\omega$ (that you call $L$, but I believe it is not "my" $L$) looks bigger than the language $L$ that I've given above (by bigger I mean it includes (infinite) strings whose prefix $a$ is repeated $n$ times for some $n \notin S$, and thus "out" of my definition of $L$. Am I wrong? $\endgroup$ – FSp Mar 29 '14 at 21:36

If $L'$ is regular then it is easy to extend a DFA for $L'$ to a deterministic Büchi automaton for $L$. For the other direction, start with a (general) Büchi automaton for $L$. Call a state winning if the automaton accepts starting at the state upon reading $x^\omega$. Remove all $x$ transitions and make winning states accepting to obtain an NFA for $L'$.


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.