Ω-reguläre Sprache

Ω-reguläre Sprache

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 Σ wird mit Σω bezeichnet. Teilmengen aus Σω heißen ω-Sprachen.

Definition

Seien Σ 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ω 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.


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Reguläre Sprache — In der theoretischen Informatik ist eine reguläre Sprache eine formale Sprache, die einigen Einschränkungen unterliegt. Reguläre Sprachen können von endlichen Automaten erkannt werden und von regulären Ausdrücken beschrieben werden.… …   Deutsch Wikipedia

  • Reguläre Ausdrücke — In der Informatik ist ein Regulärer Ausdruck (engl. regular expression, Abk. RegExp oder Regex) eine Zeichenkette, die der Beschreibung von Mengen beziehungsweise Untermengen von Zeichenketten mit Hilfe bestimmter syntaktischer Regeln dient.… …   Deutsch Wikipedia

  • Reguläre Grammatik — Eine reguläre Grammatik ist eine formale Grammatik vom Typ 3 der Chomsky Hierarchie. Die von solchen Grammatiken erzeugte Sprachen heißen reguläre Sprachen.[1] Inhaltsverzeichnis 1 Definition 1.1 Rechtsreguläre Grammatiken …   Deutsch Wikipedia

  • Reguläre Halbgruppe — Halbgruppe (Axiome EA) berührt die Spezialgebiete Mathematik Abstrakte Algebra Gruppentheorie ist Spezialfall von Magma (Axiom E) …   Deutsch Wikipedia

  • Typ-0-Sprache — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Typ-1-Sprache — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Typ-2-Sprache — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Typ-3-Sprache — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Kontextfreie Sprache — In der Theoretischen Informatik ist eine kontextfreie Sprache (engl. context free language, CFL) eine formale Sprache, die durch eine kontextfreie Grammatik beschrieben werden kann. Eine kontextfreie Grammatik erlaubt einen definierten… …   Deutsch Wikipedia

  • Lineare Sprache — Die Linearen Sprachen (engl. linear languages, LIN) sind ein Fachbegriff aus der Theoretischen Informatik. So sind sie hier speziell eine Klasse formaler Sprachen und stellen dabei eine echte Teilmenge der Typ 2 Sprachen der Chomsky Hierarchie… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”