# Proving that the continuation of a non-regular language is not ω-regular

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?

• $\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. – Karolis Juodelė Mar 29 '14 at 19:09
• actually you are right, but I explained myself very badly ... I try to amend my question ... – FSp Mar 29 '14 at 20:16
• @KarolisJuodelė I think the edit answers your query? – Raphael Mar 29 '14 at 20:45
• 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$. – David Richerby Mar 29 '14 at 21:27
• @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? – 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'$.