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

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 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 @username stuff? Otherwise it does not appear in the inbox, I passed by your comment by coincidence $\endgroup$ – Ilya Mar 25 '13 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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