Ω-reguläre Sprache
# Ω-reguläre Sprache

In der theoretischen Informatik bezeichnet die Klasse der ω-regulären Sprachen eine bestimmte Menge formaler Sprachen aus unendlichen Wörtern. Das Äquivalent im endlichen Fall ist die Klasse der regulären Sprachen.

Der griechische Buchstabe ω (omega) steht hier für die kleinste unendliche Ordinalzahl.

Der Schwerpunkt der Untersuchung ω-regulärer Sprachen liegt in der Automatentheorie. Es lässt sich beispielsweise zeigen, dass die ω-regulären Sprachen genau die Büchi-erkennbaren Sprachen sind.

## Unendliche Wörter

Ein unendliches Wort ist eine abzählbar unendliche Sequenz von Zeichen aus einem endlichen Alphabet. Über dem Alphabet $\{0,1\}$ kann z. B. das unendliche Wort $0101111111\ldots$ gebildet werden. Mengen von unendlichen Wörtern werden ω-Sprachen genannt.

Formal bedeutet dies:

Sei $\Sigma$ ein Alphabet, dann ist die Menge $\Sigma ^{\omega }$ aller unendlichen Wörter über $\Sigma$ definiert als die Menge aller Abbildungen von $\mathbb {N}$ nach $\Sigma$.

Jede Teilmenge von $\Sigma ^{\omega }$ heiße ω-Sprache.

Die ω-regulären Sprachen machen nun eine bestimmte Teilklasse der ω-Sprachen aus.

## Definition

Die Definition der ω-regulären Sprachen erfolgt rekursiv. Sei dazu $U\subseteq \Sigma ^{+}$ eine reguläre Sprache, die nicht das leere Wort enthält. Dabei bezeichne $\Sigma ^{+}$ die positive Hülle von $\Sigma$.

Dann ist $U^{\omega }$ die Menge aller abzählbar unendlichen Konkatenationen von Wörtern aus $U$.

Es gilt nun:

* $U^{\omega }$ ist eine ω-reguläre Sprache.

Seien außerdem $L_{1};L_{2}$ zwei ω-reguläre Sprachen, dann gilt weiter:

* $U\circ L_{1},L_{1}\cup L_{2}$ und $L_{1}\cap L_{2}$ sind ebenfalls ω-reguläre Sprachen.
* Außer den so konstruierten gibt es keine ω-regulären Sprachen.

Für die in der Definition verwendeten Verknüpfungen siehe auch: Formale Sprache#Operationen auf formalen Sprachen

