# Measurability of an $\omega$-regular language

It the previous question of mine I put a reference which shows that any $\omega$-regular language over the alphabet $\Sigma$ is a Borel subset of $\Sigma^\omega$. I am not sure whether the reference I am aware of is the first the showed this result, so I wonder whether there are other papers the contain it. Alternatively, I am also interested in textbooks that contain the proof of this fact.

## 1 Answer

An $\omega$-regular language is actually quite low in the Borel hierarchy (inside $\Delta_3$), a result due to

R. McNaughton, Testing and generating infinite sequences by a finite automaton, Information and Control 9 (1966), 521-530.

For a proof and more details, you can look at Chapter 3 of the following book

D. Perrin et J.-É. Pin, Infinite words, Pure and Applied Mathematics Vol 141, Elsevier, 2004, ISBN 0-12-532111-2.

• Thank you for the answer. Unfortunately, the paper by McNaughton does not seem to be accessible, and my library does not have the book you've mentioned. Perhaps, I can try convincing them to buy it.
– Ilya
Aug 7, 2013 at 6:38
• McNaughton's paper can be found here [sciencedirect.com/science/journal/00199958/9/5] Aug 7, 2013 at 10:00