<p>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.</p>

<p>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&gt;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\}$.</p>

CC BY-SA 3.0
2013-03-25T13:09:08.400Z
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
CC BY-SA 3.0
2013-03-25T15:19:49.957Z
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?
SBF
CC BY-SA 3.0
2013-03-25T15:56:20.940Z
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
CC BY-SA 3.0
2013-03-25T16:00:39.880Z
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
SBF
CC BY-SA 4.0
2019-12-13T09:29:43.583Z
Nitpick: it's Bowen Alpern and Fred Schneider. Joseph Halpern did a lot of great things but didn't contribute to this paper.
Kai
CC BY-SA 3.0
2013-03-25T12:44:04.157Z
2013-03-25T12:44:04.157Z
Klaus Draeger
<p>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 <a href="http://www.inf.u-szeged.hu/actacybernetica/edb/vol11n3/pdf/Lam_1994_ActaCybernetica.pdf">here</a> 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.</p>

<lo.logic><fl.formal-languages><automata-theory><omega-language>
Measurable language which is not $\omega$-regular
SBF
# Measurable language which is not $\omega$-regular

(Asked by: username_0 on 2013-03-25)

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](http://www.inf.u-szeged.hu/actacybernetica/edb/vol11n3/pdf/Lam_1994_ActaCybernetica.pdf) 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.

**Tags:** lo.logic, fl.formal-languages, automata-theory, omega-language


---

## 1 answers

### Answer by username_1 on 2013-03-25. Score: 11 | Accepted 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\}$.

> **Comments:**
> **username_2**: 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.  
> **username_0**: 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?  
> **username_1**: 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".  
> **username_0**: 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  
> **username_3**: Nitpick: it's Bowen Alpern and Fred Schneider. Joseph Halpern did a lot of great things but didn't contribute to this paper.  

---

