Omega-regular language
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computer science and formal language theory, the ω-regular languages are a class of ω-languages that generalize the definition of regular languages to infinite words. As regular languages accept finite strings (such as strings beginning in an a, or strings alternating between a and b), ω-regular languages accept infinite words (such as, infinite sequences beginning in an a, or infinite sequences alternating between a and b).
In computer science and formal language theory, the ω-regular languages are a class of ω-languages that generalize the definition of regular languages to infinite words. As regular languages accept finite strings (such as strings beginning in an a, or strings alternating between a and b), ω-regular languages accept infinite words (such as, infinite sequences beginning in an a, or infinite sequences alternating between a and b).
Note that if A is regular, A ω is not necessarily ω-regular, since A could be for example {ε}, the set containing only the empty string, in which case A ω =A, which is not an ω-language and therefore not an ω-regular language. It is a straightforward consequence of the definition that the ω-regular languages are precisely the ω-languages of the form A 1 B 1 ω ∪ ... ∪ A n B n ω for some n, where the A i s and B i s are regular languages and the B i s do not contain the empty string.
Equivalence to Büchi automaton
Conversely, for a given Büchi automaton , we construct an ω-regular language and then we will show that this language is recognized by A. For an ω-word w = a 1 a 2 ... let w(i,j) be the finite segment a i+1 ...a j−1 a j of w. For every , we define a regular language L q,q' that is accepted by the finite automaton .
Text derived from https://en.wikipedia.org/w/index.php?oldid=1378824723 under CC BY-SA 4.0; modifications have been made.