fbpx
Wikipedia

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.

Ein unendliches Wort ist eine abzählbar unendliche Sequenz von Zeichen aus einem endlichen Alphabet. Über dem Alphabet { 0 , 1 } {\displaystyle \{0,1\}} kann z. B. das unendliche Wort 0101111111 {\displaystyle 0101111111\ldots } gebildet werden. Mengen von unendlichen Wörtern werden ω-Sprachen genannt.

Formal bedeutet dies:

Sei Σ {\displaystyle \Sigma } ein Alphabet, dann ist die Menge Σ ω {\displaystyle \Sigma ^{\omega }} aller unendlichen Wörter über Σ {\displaystyle \Sigma } definiert als die Menge aller Abbildungen von N {\displaystyle \mathbb {N} } nach Σ {\displaystyle \Sigma } .

Jede Teilmenge von Σ ω {\displaystyle \Sigma ^{\omega }} heiße ω-Sprache.

Die ω-regulären Sprachen machen nun eine bestimmte Teilklasse der ω-Sprachen aus.

Die Definition der ω-regulären Sprachen erfolgt rekursiv. Sei dazu U Σ + {\displaystyle U\subseteq \Sigma ^{+}} eine reguläre Sprache, die nicht das leere Wort enthält. Dabei bezeichne Σ + {\displaystyle \Sigma ^{+}} die positive Hülle von Σ {\displaystyle \Sigma } .

Dann ist U ω {\displaystyle U^{\omega }} die Menge aller abzählbar unendlichen Konkatenationen von Wörtern aus U {\displaystyle U} .

Es gilt nun:

  • U ω {\displaystyle U^{\omega }} ist eine ω-reguläre Sprache.

Seien außerdem L 1 ; L 2 {\displaystyle L_{1};L_{2}} zwei ω-reguläre Sprachen, dann gilt weiter:

  • U L 1 , L 1 L 2 {\displaystyle U\circ L_{1},L_{1}\cup L_{2}} und L 1 L 2 {\displaystyle L_{1}\cap L_{2}} 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

  • 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.
w regulare Sprache Klasse formaler Sprachen Sprache Beobachten Bearbeiten Weitergeleitet von W regular In der theoretischen Informatik bezeichnet die Klasse der w regularen Sprachen eine bestimmte Menge formaler Sprachen aus unendlichen Wortern Das Aquivalent im endlichen Fall ist die Klasse der regularen Sprachen Der griechische Buchstabe w omega steht hier fur die kleinste unendliche Ordinalzahl Der Schwerpunkt der Untersuchung w regularer Sprachen liegt in der Automatentheorie Es lasst sich beispielsweise zeigen dass die w regularen Sprachen genau die Buchi erkennbaren Sprachen sind Unendliche Worter BearbeitenEin unendliches Wort ist eine abzahlbar unendliche Sequenz von Zeichen aus einem endlichen Alphabet Uber dem Alphabet 0 1 displaystyle 0 1 kann z B das unendliche Wort 0101111111 displaystyle 0101111111 ldots gebildet werden Mengen von unendlichen Wortern werden w Sprachen genannt Formal bedeutet dies Sei S displaystyle Sigma ein Alphabet dann ist die Menge S w displaystyle Sigma omega aller unendlichen Worter uber S displaystyle Sigma definiert als die Menge aller Abbildungen von N displaystyle mathbb N nach S displaystyle Sigma Jede Teilmenge von S w displaystyle Sigma omega heisse w Sprache Die w regularen Sprachen machen nun eine bestimmte Teilklasse der w Sprachen aus Definition BearbeitenDie Definition der w regularen Sprachen erfolgt rekursiv Sei dazu U S displaystyle U subseteq Sigma eine regulare Sprache die nicht das leere Wort enthalt Dabei bezeichne S displaystyle Sigma die positive Hulle von S displaystyle Sigma Dann ist U w displaystyle U omega die Menge aller abzahlbar unendlichen Konkatenationen von Wortern aus U displaystyle U Es gilt nun U w displaystyle U omega ist eine w regulare Sprache Seien ausserdem L 1 L 2 displaystyle L 1 L 2 zwei w regulare Sprachen dann gilt weiter U L 1 L 1 L 2 displaystyle U circ L 1 L 1 cup L 2 und L 1 L 2 displaystyle L 1 cap L 2 sind ebenfalls w regulare Sprachen Ausser den so konstruierten gibt es keine w regularen Sprachen Fur die in der Definition verwendeten Verknupfungen siehe auch Formale Sprache Operationen auf formalen SprachenLiteratur BearbeitenDominique Perrin Jean Eric 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 w 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 Abgerufen von https de wikipedia org w index php title W regulare Sprache amp oldid 155260933, wikipedia, wiki, deutsches, deutschland,

buch

, bücher, bibliothek,

artikel

, lesen, herunterladen, kostenlos, kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele