# Measurable language which is not $\omega$-regular

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

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\}$.

• 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. – Denis Mar 25 '13 at 13:09
• 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? – Ilya Mar 25 '13 at 15:19
• 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". – Klaus Draeger Mar 25 '13 at 15:56
• 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 – Ilya Mar 25 '13 at 16:00
• Nitpick: it's Bowen Alpern and Fred Schneider. Joseph Halpern did a lot of great things but didn't contribute to this paper. – Kai Dec 13 '19 at 9:29