# Omega language

An **ω-language** is a set of infinite-length sequences of symbols.

## Formal definition

Let Σ be a set of symbols (not necessarily finite). Following the standard definition from formal language theory, Σ^{*} is the set of all *finite* words over Σ. Every finite word has a length, which is a natural number. Given a word *w* of length *n*, *w* can be viewed as a function from the set {0,1,...,*n*−1} → Σ, with the value at *i* giving the symbol at position *i*. The infinite words, or ω-words, can likewise be viewed as functions from [math]\displaystyle{ \mathbb{N} }[/math] to Σ. The set of all infinite words over Σ is denoted Σ^{ω}. The set of all finite *and* infinite words over Σ is sometimes written Σ^{∞}.

Thus, an ω-language *L* over Σ is a subset of Σ^{ω}.

## Operations

Some common operations defined on ω-languages are:

- Intersection and union
- Given ω-languages
*L*and*M*, both*L*∪*M*and*L*∩*M*are ω-languages. - Left concatenation
- Let
*L*be an ω-language, and*K*be a language of finite words only. Then*K*can be concatenated on the left*only*to*L*to yield the new ω-language*KL*. - Omega (infinite iteration)
- As the notation hints, the operation [math]\displaystyle{ (\cdot)^\omega }[/math] is the infinite version of the Kleene star operator on finite-length languages. Given a formal language
*L*,*L*^{ω}is the ω-language of all infinite sequences of words from*L*; in the functional view, of all functions [math]\displaystyle{ \mathbb{N} \to L }[/math]. - Prefixes
- Let
*w*be an ω-word. Then the formal language Pref(*w*) contains every*finite*prefix of*w*. - Limit
- Given a finite-length language
*L*, an ω-word*w*is in the*limit*of*L*if and only if Pref(*w*) ∩*L*is an*infinite*set. In other words, for an arbitrarily large natural number*n*, it is always possible to choose some word in*L*, whose length is greater than*n*,*and*which is a prefix of*w*. The limit operation on*L*can be written*L*^{δ}or [math]\displaystyle{ \vec{L} }[/math].

## Distance between ω-words

The set Σ^{ω} can be made into a metric space by definition of the metric [math]\displaystyle{ d:\Sigma^\omega \times \Sigma^\omega \rightarrow \mathbb{R} }[/math] as:

- [math]\displaystyle{ d(w, v)=\inf \{2^{-|x|} : x\in \Sigma^*\ \text{and}\ x\in \text{Pref}(w)\cap\text{Pref}(v)\} }[/math]

where |*x*| is interpreted as "the length of *x*" (number of symbols in *x*), and **inf** is the infimum over sets of real numbers. If [math]\displaystyle{ w=v }[/math] then there is no longest prefix *x* and so [math]\displaystyle{ d(w, v)=0 }[/math]. Symmetry is clear. Transitivity follows from the fact that if *w* and *v* have a maximal shared prefix of length *m* and *v* and *u* have a maximal shared prefix of length *n* then the first [math]\displaystyle{ \min \{m, n\} }[/math] characters of *w* and *u* must be the same so [math]\displaystyle{ d(w,u)\le 2^{-\min \{m,n\}}\le 2^{-m}+2^{-n}=d(w,v)+d(v,u) }[/math]. Hence *d* is a metric.

## Important subclasses

The most widely used subclass of the ω-languages is the set of ω-regular languages, which enjoy the useful property of being recognizable by Büchi automata. Thus the decision problem of ω-regular language membership is decidable using a Büchi automaton, and fairly straightforward to compute.

If the language Σ is the power set of a set (called the "atomic propositions") then the ω-language is a linear time property, which are studied in model checking.

## Bibliography

- Perrin, D. and Pin, J-E. "Infinite Words: Automata, Semigroups, Logic and Games". Pure and Applied Mathematics Vol 141, Elsevier, 2004.
- Staiger, L. "ω-Languages". In G. Rozenberg and A. Salomaa, editors,
*Handbook of Formal Languages*, Volume 3, pages 339-387. Springer-Verlag, Berlin, 1997. - Thomas, W. "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 only URLs for external sources. (2021) (Learn how and when to remove this template message) |

This article does not cite any external source. HandWiki requires at least one external source. See citing external sources. (2021) (Learn how and when to remove this template message) |

Original source: https://en.wikipedia.org/wiki/Omega language.
Read more |