Ω-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 ${\displaystyle \{0,1\}}$ kann z. B. das unendliche Wort ${\displaystyle 0101111111\ldots }$ gebildet werden. Mengen von unendlichen Wörtern werden ω-Sprachen genannt.

Formal bedeutet dies:

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

Jede Teilmenge von ${\displaystyle \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 ${\displaystyle U\subseteq \Sigma ^{+}}$ eine reguläre Sprache, die nicht das leere Wort enthält. Dabei bezeichne ${\displaystyle \Sigma ^{+}}$ die positive Hülle von ${\displaystyle \Sigma }$.

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

Es gilt nun:

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

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

• ${\displaystyle U\circ L_{1},L_{1}\cup L_{2}}$ und ${\displaystyle 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

Literatur

• Dominique Perrin, Jean-Éric Pin: Infinite Words Automata, Semigroups, Logic and Games (= Pure and Applied Mathematics. Bd. 141). Elsevier – Academic Press, Amsterdam u. a. 2004, ISBN 0-12-532111-2.
• Ludwig Staiger: ω-Languages. In: Grzegorz Rozenberg, Arto Salomaa (Hrsg.): Handbook of Formal Languages. Band 3: Beyond Words. Springer, Berlin u. a. 1997, ISBN 3-540-60649-1, S. 339–387.
• Wolfgang Thomas: Automata on Infinite Objects. In: Jan van Leeuwen (Hrsg.): Handbook of Theoretical Computer Science. Band B: Formal Models and Semantics. Elsevier Science Publishers u. a., Amsterdam u. a. 1990, ISBN 0-444-88074-7, S. 133–192.