Omega-regular language

Uses your system voice; voice and rate in settings.

Snapshot

≈ 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.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.