Omega-regular language
From Wikipedia, the free encyclopedia
The omega-regular languages are a class of omega languages which generalize the definition of regular languages to infinite words.
[edit] 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
[edit] 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 A∩B and Σω - 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 {ε}, 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.
[edit] 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.
