ω-regulär

In der theoretischen Informatik bezeichnet eine ω-reguläre Sprache eine Menge unendlicher Wörter über einem gemeinsamen Alphabet, die gewissen Gesetzmäßigkeiten genügt. Im Fall von endlichen Wörtern heißt das Äquivalent reguläre Sprache.

Häufig wird diese Sprachklasse in der Automatentheorie genutzt. Die ω-reguläre Sprachen akzeptierenden Automaten heißen ω-Automaten.

Unendliche Wörter

Ein unendliches Wort ist eine unendliche Sequenz von Zeichen aus einem Alphabet. Man kann dies über eine Abbildung mithilfe der natürlichen Zahlen ${\N}$ formalisieren, bei der jeder Position im Wort der dort befindliche Buchstabe zugewiesen wird. Über dem Alphabet $\{0,1\}$ kann z.B. das unendliche Wort $0101111111\ldots$ gebildet werden.

Die Menge der unendlichen Wörter über einem Alphabet $\Sigma$ wird mit $\Sigma^{\omega}$ bezeichnet. Teilmengen aus $\Sigma^{\omega}$ heißen ω-Sprachen.

Definition

Seien $\Sigma$ ein endliches Alphabet, $U \subseteq \Sigma^*$ eine reguläre Sprache und $L_1,L_2 \subseteq \Sigma^{\omega}$ zwei ω-reguläre Sprachen, dann gilt:

• $U^{\omega}$ ist eine ω-reguläre Sprache
• $U \cdot L_1$ ist eine ω-reguläre Sprache
• $L_1 \cup L_2$ und $L_1 \cap L_2$ sind ω-reguläre Sprachen.

Mit dieser Vorschrift können alle ω-regulären Sprachen konstruiert werden.

Die ω-regulären Sprachen sind genau die büchi-erkennbaren Sprachen.