|
The omega-regular languages are a class of omega languages which generalize the definition of regular languages to infinite words.
Formal definition
An omega-language L is omega-regular if it has the form
- A? where A is a regular language
- AB, the concatenation of a regular language A and an omega-regular language B (Note that BA is not well-defined)
- A?B where A and B are omega-regular languages
Properties
Every omega-regular language is accepted by a nondeterministic Büchi automaton; the translation is constructive.
Using Büchi automata, it can be proved that if A and B are omega-regular languages, then AnB and S? - A, the complement of A, are omega-regular languages.
Büchi's main result was that omega-regular languages are precisely the ones definable in a particular monadic second-order logic called S1S. Linear temporal logic is a fragment of S1S.
Note that if A is regular, A? is not necessarily omega-regular, since A could be {e}, the set containing only the empty string, in which case A?=A, which is not an omega-language and therefore not an omega-regular language.
Bibliography
- W. Thomas, "Automata on infinite objects." In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B: Formal Models and Semantics, pages 133-192. Elsevier Science Publishers, Amsterdam, 1990.
| |
