Let $\Sigma$ be a finite alphabet and let $\Sigma^\omega$ be the set of all infinite words over $\Sigma$. Consider $$ d(x,y):=2^{-\min(n \in \Bbb N_0:x_n\neq y_n)} $$ to be the metric on $\Sigma^\omega$ which makes the latter being the Cantor space. Denote by $\mathscr B(\Sigma^\omega)$ the Borel $\sigma$-algebra of this space, and let's call its elements measurable languages. It follows from Proposition 6 here that any $\omega$-regular language is measurable. I am looking for an example of a measurable language which is not $\omega$-regular, so any hints are appreciated.


1 Answer 1


A simple class of examples can be found by considering singleton languages $\{w\}$. These are measurable (Let $C_n(w)$ be the set of words agreeing with $w$ up to the $n$-th letter, then $\{w\}$ is the intersection of all $C_n(w)$). However, unless $w$ is eventually periodic, the language is not $\omega$-regular.

For a concrete example, consider the word $w=ababbabbba\dots$. If $w$ is accepted by a nondeterministic Büchi automaton $A$ with $k$ states, then while parsing the $n$-th block of $b$s, with $n>k$, $A$ needs to visit some state twice, so we can construct another word accepted by $A$ by pumping this block suitably. Therefore no automaton recognizes $\{w\}$.

  • 4
    $\begingroup$ One can also obtain non-regular languages at arbitrary Borel levels, by adding a nonperiodic $w$ to a regular language $L$ (with $w\notin L$). The resulting language $L'=L\cup\{w\}$ will always be non-regular, because otherwie $L'\setminus L=\{w\}$ would also be regular. $\endgroup$
    – Denis
    Commented Mar 25, 2013 at 13:09
  • $\begingroup$ That's a very insightful answer, thank you very much. Can you suggest many any "canonical" references dealing with Borel structures over $\Sigma^\omega$? I've only seen the paper I cited in OP, but it only touches upon a few number of concepts. Clearly, $\Sigma^\omega$ is just a Cantor space, but I'm interested how the topological/measure-theoretical properties of it are related to those of regularity etc. For example, if I'm not mistaken, regular languages (embedded in $\Sigma^\omega$) are precisely open sets? $\endgroup$
    – SBF
    Commented Mar 25, 2013 at 15:19
  • $\begingroup$ Not sure about "canonical", but two starting points would be (1) Halpern and Schneider, Defining Liveness (contains the characterization safety = closed and liveness = dense), and (2) numerous papers by Alain Finkel, in particular "Borel Hierarchy and Omega Context Free Languages". $\endgroup$ Commented Mar 25, 2013 at 15:56
  • $\begingroup$ Cool, I'll take a look into those sources - perhaps references there will also steer me. Btw, could you please use this @username stuff? Otherwise it does not appear in the inbox, I passed by your comment by coincidence $\endgroup$
    – SBF
    Commented Mar 25, 2013 at 16:00
  • $\begingroup$ Nitpick: it's Bowen Alpern and Fred Schneider. Joseph Halpern did a lot of great things but didn't contribute to this paper. $\endgroup$
    – Kai
    Commented Dec 13, 2019 at 9:29

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.