Ω-reguläre Sprache

Grundidee und Bedeutung

Eine ω-reguläre Sprache ist eine formale Sprache, deren Wörter unendlich lang sind. Die Klasse der ω-regulären Sprachen entspricht damit im Bereich unendlicher Wörter der Klasse der regulären Sprachen für endliche Wörter. Der Buchstabe ω bezeichnet dabei die kleinste unendliche Ordinalzahl.

ω-reguläre Sprachen werden vor allem in der Automatentheorie untersucht. Sie sind genau die Büchi-erkennbaren Sprachen, also diejenigen Sprachen unendlicher Wörter, die durch Büchi-Automaten erkannt werden können.

Unendliche Wörter und ω-Sprachen

Ein unendliches Wort ist eine abzählbar unendliche Folge von Zeichen aus einem endlichen Alphabet. Über dem Alphabet {0,1} ist beispielsweise 0101111111… ein unendliches Wort.

Sei Σ ein Alphabet. Dann bezeichnet Σ^ω die Menge aller unendlichen Wörter über Σ. Formal ist Σ^ω die Menge aller Abbildungen von ℕ nach Σ: Jeder natürlichen Zahl wird also das Zeichen zugeordnet, das an der entsprechenden Stelle des Wortes steht.

Jede Teilmenge von Σ^ω heißt ω-Sprache. Die ω-regulären Sprachen bilden eine bestimmte Teilklasse dieser ω-Sprachen.

Rekursive Definition

Die Klasse der ω-regulären Sprachen wird rekursiv festgelegt. Sei U ⊆ Σ^+ eine reguläre Sprache, die das leere Wort nicht enthält. Dabei ist Σ^+ die positive Hülle von Σ, also die Menge aller nichtleeren endlichen Wörter über Σ.

U^ω ist die Menge aller abzählbar unendlichen Konkatenationen von Wörtern aus U. Eine Konkatenation ist das Aneinanderhängen von Wörtern. Für jede solche reguläre Sprache U gilt:

• U^ω ist eine ω-reguläre Sprache.

Sind L₁ und L₂ bereits ω-reguläre Sprachen, so sind auch folgende Sprachen ω-regulär:

• U ∘ L₁: Ein endliches Wort aus U wird mit einem unendlichen Wort aus L₁ verkettet.

• L₁ ∪ L₂: die Vereinigung beider Sprachen.

• L₁ ∩ L₂: der Durchschnitt beider Sprachen.

Außer den Sprachen, die sich durch diese Ausgangsregel und diese Operationen konstruieren lassen, gibt es keine weiteren ω-regulären Sprachen.