The omega-regular languages are a class of omega languages which generalize the definition of regular languages to infinite words.
An omega-language L is omega-regular if it has the form
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 languag...
more
The omega-regular languages are a class of omega languages which generalize the definition of regular languages to infinite words.
An omega-language L is omega-regular if it has the form
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.
less
