Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Proving that the continuation of a non-regular language is not ω-regular

, ,
Problem Detail:

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?

#### Answered By : Yuval Filmus

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

Question Source : http://cs.stackexchange.com/questions/23227

3.2K people like this