Reguläre Sprache - LinkFang.de





Reguläre Sprache


In der theoretischen Informatik ist eine reguläre Sprache oder reguläre Menge 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.

Eigenschaften

Ob eine Sprache mehr oder weniger eingeschränkt ist, ergibt sich aus ihrer Stellung innerhalb der Chomsky-Hierarchie. Die Klasse der regulären Sprachen entspricht innerhalb der Chomsky-Hierarchie der am meisten eingeschränkten Sprachklasse vom Typ 3. Sie bildet eine echte Teilmenge der kontextfreien Sprachen. Sie hat in der Informatik eine große praktische Bedeutung.

Definition

Eine Sprache [math]L[/math] über einem Alphabet [math]\Sigma[/math], also eine Menge von Wörtern [math]L\subseteq \Sigma^{*}[/math], heißt dann regulär, wenn sie eine der folgenden äquivalenten Bedingungen erfüllt:

  • [math]L[/math] wird von einer regulären Grammatik erzeugt.
  • [math]L[/math] wird von einem endlichen Automaten akzeptiert.
  • [math]L[/math] kann durch einen regulären Ausdruck dargestellt werden.
  • Die auf [math]\Sigma^{*}[/math] durch [math](x,y)\in R_L :\Leftrightarrow (\forall z\in \Sigma^{*}:(xz\in L\Leftrightarrow yz\in L))[/math] definierte Relation [math]R_L[/math] hat endlichen Index (Satz von Myhill-Nerode).
  • [math]L[/math] kann in der Monadischen Logik 2. Stufe definiert werden

Nachweis der Regularität einer Sprache

Will man für eine gegebene Sprache nachweisen, dass sie regulär ist, so muss man sie demnach auf eine reguläre Grammatik, einen endlichen Automaten (z. B. einen Moore-Automaten) oder einen regulären Ausdruck oder auf bereits bekannte reguläre Sprachen zurückführen. Für einen Nachweis, dass eine Sprache [math]L[/math] nicht regulär ist, ist es meistens zweckmäßig, das Pumping-Lemma (= Pumplemma) für reguläre Sprachen zu benutzen oder in schwierigeren Fällen nachzuweisen, dass der Index von [math]R_L[/math] nicht endlich ist.

Beispiele

Sei [math]\Sigma[/math] ein Alphabet.

  • Alle endlichen Sprachen [math]L[/math] über [math]\Sigma[/math], d. h. solche mit [math]\left| L \right|\in\mathbb{N}[/math], sind regulär.
  • Alle kontextfreien Sprachen über einem unären Alphabet, d. h. solche mit [math]\left|\Sigma\right|=1[/math], sind regulär.

Abschlusseigenschaften

Die Klasse der regulären Sprachen ist abgeschlossen unter den gewöhnlichen Mengenoperationen Vereinigung, Durchschnitt und Komplement. Darüber hinaus gilt die Abgeschlossenheit auch für die Konkatenation und den sogenannten Kleene-Stern sowie die Differenzmenge. Im Einzelnen gilt also:

  • Die Vereinigung [math]L = L_1 \cup L_2[/math] zweier regulärer Sprachen [math]L_1[/math] und [math]L_2[/math] ist regulär.
  • Der Schnitt [math]L = L_1\cap L_2[/math] zweier regulärer Sprachen [math]L_1[/math] und [math]L_2[/math] ist regulär.
  • Das Komplement [math]\overline{L}[/math] einer regulären Sprache [math]L[/math] ist regulär.
  • Die Konkatenation [math]\{uv \mid u\in L_1 \and v\in L_2\}[/math] zweier regulärer Sprachen [math]L_1[/math] und [math]L_2[/math] ist regulär.
  • Der Kleene-Stern [math]L^{*}[/math] einer regulären Sprache [math]L[/math], d. h. die beliebig häufige Konkatenation von Wörtern aus der Sprache [math]L[/math] vereinigt mit dem leeren Wort, ist regulär.
  • Die Differenz [math]L = L_1\setminus L_2[/math] zweier regulärer Sprachen [math]L_1[/math] und [math]L_2[/math] ist regulär.[1]

Typische Entscheidungsprobleme

Seien [math]L[/math], [math]L_1[/math] und [math]L_2[/math] gegebene reguläre Sprachen über dem Alphabet [math]\Sigma[/math]. Dann ergeben sich folgende typische Problemstellungen:

Alle diese Probleme sind entscheidbar. Bis auf das Äquivalenzproblem und das Inklusionsproblem sind die genannten Probleme auch bei kontextfreien Sprachen (der nach der Chomsky-Hierarchie nächsthöheren Sprachklasse) entscheidbar.

Literatur

  • Michael Sipser: Introduction to the Theory of Computation. PWS Publishing, Boston u. a. 1997, ISBN 0-534-94728-X, Chapter 1: Regular Languages.
  • Uwe Schöning: Theoretische Informatik – kurzgefasst. 4. Auflage. Spektrum, Heidelberg u. a. 2001, ISBN 3-8274-1099-1, (Spektrum-Hochschultaschenbuch), Kapitel 1.2: Reguläre Sprachen.
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie. Formale Sprachen und Komplexitätstheorie. 2. überarbeitete Auflage. Pearson Studium, München 2002, ISBN 3-8273-7020-5, (i - Informatik).
  • Dag Hovland: The Inclusion Problem for Regular Expressions. In: LNCS Language and Automata Theory and Applications. Bd. 6031, 2010, S. 309–320, doi:10.1007/978-3-642-13089-2_26 (PDF ).

Weblinks

  • REG . In: Complexity Zoo. (englisch)

Einzelnachweise und Anmerkungen

  1. Das ergibt sich schon aus den Abschlusseigenschaften von Schnitt und Komplement, da [math]L_1\setminus L_2 = L_1 \cap \overline{L_2}[/math]ist.

Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Reguläre Sprache (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.