Hauptmenü öffnen

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.

EigenschaftenBearbeiten

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.

DefinitionBearbeiten

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:

  •   wird von einer regulären Grammatik erzeugt.
  •   wird von einem endlichen Automaten akzeptiert.
  •   kann durch einen regulären Ausdruck dargestellt werden.
  • Die auf   durch   definierte Relation   hat endlichen Index (Satz von Myhill-Nerode).
  •   kann in der Monadischen Logik 2. Stufe definiert werden.

Nachweis der Regularität einer SpracheBearbeiten

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.

BeispieleBearbeiten

  •   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.

AbschlusseigenschaftenBearbeiten

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.[1]

Typische EntscheidungsproblemeBearbeiten

Seien  ,   und   gegebene reguläre Sprachen über dem Alphabet  . Dann ergeben sich folgende typische Problemstellungen:

  • Wortproblem: Gehört ein Wort   zu  ?
  • Leerheitsproblem: Ist   die leere Menge?
  • Endlichkeitsproblem: Besteht   aus einer endlichen Menge von Wörtern?
  • Äquivalenzproblem: Gilt  ?
  • Inklusionsproblem: Gilt  ?

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.

LiteraturBearbeiten

  • 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).

WeblinksBearbeiten

  • REG. In: Complexity Zoo. (englisch)

Einzelnachweise und AnmerkungenBearbeiten

  1. Das ergibt sich schon aus den Abschlusseigenschaften von Schnitt und Komplement, da   ist.