www.wikidata.de-de.nina.az

Reguläre Sprache In der theoretischen Informatik ist eine reguläre Sprache oder reguläre Menge oder erkennbare Sprache e

Reguläre Sprache

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

Eigenschaften Bearbeiten

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 Bearbeiten

Eine Sprache über einem Alphabet , also eine Menge von Wörtern , heißt dann regulär, wenn sie eine der folgenden äquivalenten Bedingungen erfüllt:

Nachweis der Regularität einer Sprache Bearbeiten

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 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 nicht endlich ist.

Beispiele Bearbeiten

  • ist regulär.
  • Alle endlichen Sprachen über einem beliebigen Alphabet , d. h. solche mit , sind regulär.
    • Beispiel:
    • Auch die leere Menge ist eine reguläre Sprache.
  • Alle kontextfreien Sprachen über einem unären Alphabet, d. h. solche mit , sind regulär.
  • Die Dyck-Sprachen sind nicht regulär.

Abschlusseigenschaften Bearbeiten

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 zweier regulärer Sprachen und ist regulär.
  • Der Schnitt zweier regulärer Sprachen und ist regulär.
  • Das Komplement einer regulären Sprache ist regulär.
  • Die Konkatenation zweier regulärer Sprachen und ist regulär.
  • Der Kleene-Stern einer regulären Sprache , d. h. die beliebig häufige Konkatenation von Wörtern aus der Sprache vereinigt mit dem leeren Wort, ist regulär.
  • Die Differenz zweier regulärer Sprachen und ist regulär.

Typische Entscheidungsprobleme Bearbeiten

Seien , und gegebene reguläre Sprachen über dem Alphabet . 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 Bearbeiten

  • 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. Band 6031, 2010, S. 309–320, doi:10.1007/978-3-642-13089-2_26 (PDF).

Weblinks Bearbeiten

  • REG. In: Complexity Zoo. (englisch)

Einzelnachweise und Anmerkungen Bearbeiten

  1. Das ergibt sich schon aus den Abschlusseigenschaften von Schnitt und Komplement, da ist.
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
Veröffentlichungsdatum:
In der theoretischen Informatik ist eine regulare Sprache oder regulare Menge oder erkennbare Sprache eine formale Sprache die einigen Einschrankungen unterliegt Regulare Sprachen konnen von endlichen Automaten erkannt werden und von regularen Ausdrucken beschrieben werden Inhaltsverzeichnis 1 Eigenschaften 2 Definition 3 Nachweis der Regularitat einer Sprache 4 Beispiele 5 Abschlusseigenschaften 6 Typische Entscheidungsprobleme 7 Literatur 8 Weblinks 9 Einzelnachweise und AnmerkungenEigenschaften BearbeitenOb eine Sprache mehr oder weniger eingeschrankt ist ergibt sich aus ihrer Stellung innerhalb der Chomsky Hierarchie Die Klasse der regularen Sprachen entspricht innerhalb der Chomsky Hierarchie der am meisten eingeschrankten Sprachklasse vom Typ 3 Sie bildet eine echte Teilmenge der kontextfreien Sprachen Sie hat in der Informatik eine grosse praktische Bedeutung Definition BearbeitenEine Sprache L displaystyle L nbsp uber einem Alphabet S displaystyle Sigma nbsp also eine Menge von Wortern L S displaystyle L subseteq Sigma nbsp heisst dann regular wenn sie eine der folgenden aquivalenten Bedingungen erfullt L displaystyle L nbsp wird von einer regularen Grammatik erzeugt L displaystyle L nbsp wird von einem endlichen Automaten akzeptiert L displaystyle L nbsp kann durch einen regularen Ausdruck dargestellt werden Die auf S displaystyle Sigma nbsp durch x y R L z S x z L y z L displaystyle x y in R L Leftrightarrow forall z in Sigma xz in L Leftrightarrow yz in L nbsp definierte Relation R L displaystyle R L nbsp hat endlichen Index Satz von Myhill Nerode L displaystyle L nbsp kann in der monadischen Logik 2 Stufe definiert werden L displaystyle L nbsp ist induktiv definiert als Verankerung L a displaystyle L a nbsp mit a S displaystyle a in Sigma nbsp oder L displaystyle L emptyset nbsp oder L e displaystyle L varepsilon nbsp Induktion Fur L 1 L 2 displaystyle L 1 L 2 nbsp regulare Sprachen L L 1 L 2 displaystyle L L 1 cdot L 2 nbsp oder L L 1 L 2 displaystyle L L 1 cup L 2 nbsp oder L L displaystyle L L nbsp Nachweis der Regularitat einer Sprache BearbeitenWill man fur eine gegebene Sprache nachweisen dass sie regular ist so muss man sie demnach auf eine regulare Grammatik einen endlichen Automaten z B einen Moore Automaten oder einen regularen Ausdruck oder auf bereits bekannte regulare Sprachen zuruckfuhren Fur einen Nachweis dass eine Sprache L displaystyle L nbsp nicht regular ist ist es meistens zweckmassig das Pumping Lemma Pumplemma fur regulare Sprachen zu benutzen oder in schwierigeren Fallen nachzuweisen dass der Index von R L displaystyle R L nbsp nicht endlich ist Beispiele Bearbeiten a i b j i j N displaystyle left a i b j mid i j in mathbb N right nbsp ist regular Alle endlichen Sprachen L displaystyle L nbsp uber einem beliebigen Alphabet S displaystyle Sigma nbsp d h solche mit L N displaystyle left L right in mathbb N nbsp sind regular Beispiel a a b displaystyle left a ab right nbsp Auch die leere Menge ist eine regulare Sprache Alle kontextfreien Sprachen uber einem unaren Alphabet d h solche mit S 1 displaystyle left Sigma right 1 nbsp sind regular Die Dyck Sprachen sind nicht regular Abschlusseigenschaften BearbeitenDie Klasse der regularen Sprachen ist abgeschlossen unter den gewohnlichen Mengenoperationen Vereinigung Durchschnitt und Komplement Daruber hinaus gilt die Abgeschlossenheit auch fur die Konkatenation und den sogenannten Kleene Stern sowie die Differenzmenge Im Einzelnen gilt also Die Vereinigung L L 1 L 2 displaystyle L L 1 cup L 2 nbsp zweier regularer Sprachen L 1 displaystyle L 1 nbsp und L 2 displaystyle L 2 nbsp ist regular Der Schnitt L L 1 L 2 displaystyle L L 1 cap L 2 nbsp zweier regularer Sprachen L 1 displaystyle L 1 nbsp und L 2 displaystyle L 2 nbsp ist regular Das Komplement L S L displaystyle overline L Sigma setminus L nbsp einer regularen Sprache L displaystyle L nbsp ist regular Die Konkatenation u v u L 1 v L 2 displaystyle uv mid u in L 1 land v in L 2 nbsp zweier regularer Sprachen L 1 displaystyle L 1 nbsp und L 2 displaystyle L 2 nbsp ist regular Der Kleene Stern L displaystyle L nbsp einer regularen Sprache L displaystyle L nbsp d h die beliebig haufige Konkatenation von Wortern aus der Sprache L displaystyle L nbsp vereinigt mit dem leeren Wort ist regular Die Differenz L L 1 L 2 displaystyle L L 1 setminus L 2 nbsp zweier regularer Sprachen L 1 displaystyle L 1 nbsp und L 2 displaystyle L 2 nbsp ist regular 1 Typische Entscheidungsprobleme BearbeitenSeien L displaystyle L nbsp L 1 displaystyle L 1 nbsp und L 2 displaystyle L 2 nbsp gegebene regulare Sprachen uber dem Alphabet S displaystyle Sigma nbsp Dann ergeben sich folgende typische Problemstellungen Wortproblem Gehort ein Wort w S displaystyle w in Sigma nbsp zu L displaystyle L nbsp Leerheitsproblem Ist L displaystyle L nbsp die leere Menge Endlichkeitsproblem Besteht L displaystyle L nbsp aus einer endlichen Menge von Wortern Aquivalenzproblem Gilt L 1 L 2 displaystyle L 1 L 2 nbsp Inklusionsproblem Gilt L 1 L 2 displaystyle L 1 subseteq L 2 nbsp Alle diese Probleme sind entscheidbar Bis auf das Aquivalenzproblem und das Inklusionsproblem sind die genannten Probleme auch bei kontextfreien Sprachen der nach der Chomsky Hierarchie nachsthoheren Sprachklasse entscheidbar Literatur BearbeitenMichael Sipser Introduction to the Theory of Computation PWS Publishing Boston u a 1997 ISBN 0 534 94728 X Chapter 1 Regular Languages Uwe Schoning Theoretische Informatik kurzgefasst 4 Auflage Spektrum Heidelberg u a 2001 ISBN 3 8274 1099 1 Spektrum Hochschultaschenbuch Kapitel 1 2 Regulare Sprachen John E Hopcroft Rajeev Motwani Jeffrey D Ullman Einfuhrung in die Automatentheorie Formale Sprachen und Komplexitatstheorie 2 uberarbeitete Auflage Pearson Studium Munchen 2002 ISBN 3 8273 7020 5 i Informatik Dag Hovland The Inclusion Problem for Regular Expressions In LNCS Language and Automata Theory and Applications Band 6031 2010 S 309 320 doi 10 1007 978 3 642 13089 2 26 PDF Weblinks BearbeitenREG In Complexity Zoo englisch Einzelnachweise und Anmerkungen Bearbeiten Das ergibt sich schon aus den Abschlusseigenschaften von Schnitt und Komplement da L 1 L 2 L 1 L 2 displaystyle L 1 setminus L 2 L 1 cap overline L 2 nbsp ist Abgerufen von https de wikipedia org w index php title Regulare Sprache amp oldid 229668397