ω-reguläre Sprache

Klasse formaler Sprachen

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   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

Bearbeiten

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

Bearbeiten
  • 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.