ω-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 kann z. B. das unendliche Wort gebildet werden. Mengen von unendlichen Wörtern werden ω-Sprachen genannt.
Formal bedeutet dies:
Sei ein Alphabet, dann ist die Menge aller unendlichen Wörter über definiert als die Menge aller Abbildungen von nach .
Jede Teilmenge von 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 eine reguläre Sprache, die nicht das leere Wort enthält. Dabei bezeichne die positive Hülle von .
Dann ist die Menge aller abzählbar unendlichen Konkatenationen von Wörtern aus .
Es gilt nun:
- ist eine ω-reguläre Sprache.
Seien außerdem zwei ω-reguläre Sprachen, dann gilt weiter:
- und 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.