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

<p>R. McNaughton, Testing and generating infinite sequences by a finite automaton, <em>Information and Control</em> <strong>9</strong> (1966), 521-530.  </p>

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

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

CC BY-SA 3.0
2013-08-07T06:38:22.003Z
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.
SBF
CC BY-SA 3.0
2013-08-07T10:00:47.843Z
McNaughton's paper can be found here [http://www.sciencedirect.com/science/journal/00199958/9/5]
J.-E. Pin
CC BY-SA 3.0
2013-08-06T16:32:02.950Z
2013-08-06T16:32:02.950Z
J.-E. Pin
<p>It the previous <a href="https://cstheory.stackexchange.com/q/17016/14336">question</a> 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.</p>

<reference-request><lo.logic><fl.formal-languages><automata-theory><ho.history-overview>
Measurability of an $\omega$-regular language
SBF
# Measurability of an $\omega$-regular language

(Asked by: username_0 on 2013-08-06)

It the previous [question](https://cstheory.stackexchange.com/q/17016/14336) 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.

**Tags:** reference-request, lo.logic, fl.formal-languages, automata-theory, ho.history-overview

---

## 1 answers

### Answer by username_1 on 2013-08-06. Score: 14 | Accepted 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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: McNaughton's paper can be found here [http://www.sciencedirect.com/science/journal/00199958/9/5]  

---

