2
$\begingroup$

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?

Improve this question
$\endgroup$
10
  • 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ė
    Commented Mar 29, 2014 at 19:09
  • $\begingroup$ actually you are right, but I explained myself very badly ... I try to amend my question ... $\endgroup$
    – FSp
    Commented Mar 29, 2014 at 20:16
  • $\begingroup$ @KarolisJuodelė I think the edit answers your query? $\endgroup$
    – Raphael
    Commented Mar 29, 2014 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
    Commented Mar 29, 2014 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
    Commented Mar 29, 2014 at 21:36

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.