- Omega-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 formalisieren, bei der jeder Position im Wort der dort befindliche Buchstabe zugewiesen wird. Über dem Alphabet {0,1} kann z.B. das unendliche Wort gebildet werden.
Die Menge der unendlichen Wörter über einem Alphabet Σ wird mit Σω bezeichnet. Teilmengen aus Σω heißen ω-Sprachen.
Definition
Seien Σ ein endliches Alphabet, eine reguläre Sprache und zwei ω-reguläre Sprachen, dann gilt:
- Uω ist eine ω-reguläre Sprache
- ist eine ω-reguläre Sprache
- und 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.
Wikimedia Foundation.