/guid/9202a8c04000641f8000000000910601 rename

The omega-regular languages are a class of omega languages which generalize the definition of...

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.