Omega-regular Language

Get Omega-regular Language essential facts below. View Videos or join the Omega-regular Language discussion. Add Omega-regular Language to your PopFlock.com topic list for future reference or share this resource on social media.
## Formal definition

## Equivalence to Büchi automaton

## Bibliography

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Omega-regular Language

The **?-regular languages** are a class of ω-languages that generalize the definition of regular languages to infinite words. Büchi showed in 1962 that ?-regular languages are precisely the ones definable in a particular monadic second-order logic called S1S.

An ?-language *L* is ?-regular if it has the form

*A*^{?}where*A*is a nonempty regular language not containing the empty string*AB*, the concatenation of a regular language*A*and an ?-regular language*B*(Note that*BA*is*not*well-defined)*A*?*B*where*A*and*B*are ?-regular languages (this rule can only be applied finitely many times)

The elements of *A*^{?} are obtained by concatenating words from *A* infinitely many times.
Note that if *A* is regular, *A*^{?} is not necessarily ?-regular, since *A* could be {?}, the set containing only the empty string, in which case *A*^{?}=*A*, which is not an ?-language and therefore not an ?-regular language.

**Theorem**:* An ?-language is recognized by a Büchi automaton if and only if it is an ?-regular language.*

**Proof**: Every ?-regular language is recognized by a nondeterministic Büchi automaton; the translation is constructive. Using the closure properties of Büchi automata and structural induction over the definition of ?-regular language, it can be easily shown that a Büchi automaton can be constructed for any given ?-regular language.

Conversely, for a given Büchi automaton *A* = (*Q*, ?, ?, *I*, *F*), 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 *q*, *q'* ? *Q*, we define a regular language *L _{q,q'}* that is accepted by the finite automaton (

**Lemma:**We claim that Büchi automaton*A*recognizes language ?_{q?I,q'?F}*L*(_{q,q'}*L*- {?} )_{q',q'}^{?}.**Proof:**Let's suppose word*w*?*L(A)*and q_{0},q_{1},q_{2},... is an accepting run of*A*on*w*. Therefore, q_{0}is in*I*and there must be a state q' in*F*such that q' occurs infinitely often in the accepting run. Let's pick the increasing infinite sequence of indexes i_{0},i_{1},i_{2}... such that, for all k>=0, q_{ik}is q'. Therefore,*w*(0,i_{0})?*L*and, for all k>=0,_{q0,q'}*w*(i_{k},i_{k+1})?*L*. Therefore,_{q',q'}*w*?*L*(_{q0,q'}*L*)_{q',q'}^{?}.- Now, suppose
*w*?*L*(_{q,q'}*L*- {?} )_{q',q'}^{?}for some q?*I*and q'?*F*. Therefore, there is an infinite and strictly increasing sequence i_{0},i_{1},i_{2}... such that*w*(0,i_{0}) ?*L*and, for all k>=0,_{q,q'}*w*(i_{k},i_{k+1})?*L*. By definition of_{q',q'}*L*, there is a finite run of A from q to q' on word_{q,q'}*w*(0,i_{0}). For all k>=0, there is a finite run of A from q' to q' on word*w*(i_{k},i_{k+1}). By this construction, there is a run of*A*, which starts from q and in which q' occurs infinitely often. Hence,*w*?*L(A)*.

- W. Thomas, "Automata on infinite objects." In Jan van Leeuwen, editor,
*Handbook of Theoretical Computer Science, volume B: Formal Models and Semantics*, pages 133-192. Elsevier Science Publishers, Amsterdam, 1990.

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Popular Products

Music Scenes

Popular Artists