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.
8
$\begingroup$
$\endgroup$
-
1$\begingroup$ Did you mean $2^{-\min{\ldots}}$ ? $\endgroup$ – Shaull Mar 25 '13 at 11:07
-
$\begingroup$ @Shaull: yes, thanks a lot for mentioning it $\endgroup$ – Ilya Mar 25 '13 at 15:04
10
$\begingroup$
$\endgroup$
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\}$.
answered Mar 25 '13 at 12:44
-
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 Mar 25 '13 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$ – Ilya Mar 25 '13 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$ – Klaus Draeger Mar 25 '13 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
@usernamestuff? Otherwise it does not appear in the inbox, I passed by your comment by coincidence $\endgroup$ – Ilya Mar 25 '13 at 16:00
