ω-reguläre Sprache

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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 \N nach \Sigma.

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

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

Definition[Bearbeiten]

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