ω-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 <math>\{0,1\}</math> kann z. B. das unendliche Wort <math>0101111111\ldots</math> gebildet werden. Mengen von unendlichen Wörtern werden ω-Sprachen genannt.
Formal bedeutet dies:
Sei <math>\Sigma</math> ein Alphabet, dann ist die Menge <math>\Sigma^{\omega}</math> aller unendlichen Wörter über <math>\Sigma</math> definiert als die Menge aller Abbildungen von <math>\N</math> nach <math>\Sigma</math>.
Jede Teilmenge von <math>\Sigma^{\omega}</math> 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 <math>U \subseteq \Sigma^+</math> eine reguläre Sprache, die nicht das leere Wort enthält. Dabei bezeichne <math>\Sigma^+</math> die positive Hülle von <math>\Sigma</math>.
Dann ist <math>U^{\omega}</math> die Menge aller abzählbar unendlichen Konkatenationen von Wörtern aus <math>U</math>.
Es gilt nun:
- <math>U^{\omega}</math> ist eine ω-reguläre Sprache.
Seien außerdem <math>L_1;L_2</math> zwei ω-reguläre Sprachen, dann gilt weiter:
- <math>U \circ L_1, L_1 \cup L_2</math> und <math>L_1 \cap L_2</math> 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.