Wikipedia · einfach zusammengefasst · Stand
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 …
Inhalt5 Abschnitte
Kernidee und Bedeutung
Eine reguläre Sprache, auch reguläre Menge oder erkennbare Sprache genannt, ist eine formale Sprache mit bestimmten Einschränkungen. Eine formale Sprache über einem Alphabet Σ ist eine Menge von Wörtern, also L ⊆ Σ*. Reguläre Sprachen können von endlichen Automaten erkannt und durch reguläre Ausdrücke beschrieben werden.
Diese Sprachklasse ist in der Informatik von großer praktischer Bedeutung. In der Chomsky-Hierarchie entspricht sie den Typ-3-Sprachen und ist damit die am stärksten eingeschränkte Sprachklasse dieser Hierarchie. Die regulären Sprachen bilden eine echte Teilmenge der kontextfreien Sprachen: Jede reguläre Sprache ist kontextfrei, aber nicht jede kontextfreie Sprache ist regulär.
Gleichwertige Definitionen
Eine Sprache L über einem Alphabet Σ heißt regulär, wenn sie eine der folgenden gleichwertigen Bedingungen erfüllt:
• L wird von einer regulären Grammatik erzeugt.
• L wird von einem endlichen Automaten entschieden.
• L kann durch einen regulären Ausdruck dargestellt werden.
• Die Relation R_L auf Σ* mit (x,y) ∈ R_L genau dann, wenn für alle z ∈ Σ* gilt: xz ∈ L ⇔ yz ∈ L, hat einen endlichen Index. Das bedeutet, dass es nur endlich viele Äquivalenzklassen von Wörtern gibt, die sich hinsichtlich aller möglichen Fortsetzungen z gleich verhalten. Diese Charakterisierung ist als Satz von Myhill-Nerode bekannt.
• L kann in der monadischen Logik 2. Stufe definiert werden.
• L lässt sich induktiv aufbauen. Als Verankerung sind die einbuchstabigen Sprachen L = {a} mit a ∈ Σ, die leere Sprache L = ∅ und die Sprache L = {ε} mit dem leeren Wort ε zugelassen. Sind L₁ und L₂ bereits regulär, so sind auch ihre Konkatenation L₁ · L₂, ihre Vereinigung L₁ ∪ L₂ und der Kleene-Stern L* regulär.
Regularität nachweisen oder widerlegen
Um nachzuweisen, dass eine gegebene Sprache regulär ist, kann man eine der gleichwertigen Definitionen verwenden. Man gibt beispielsweise eine reguläre Grammatik, einen endlichen Automaten oder einen regulären Ausdruck für die Sprache an. Alternativ führt man sie mithilfe erlaubter Operationen auf Sprachen zurück, deren Regularität bereits bekannt ist.
Soll gezeigt werden, dass eine Sprache L nicht regulär ist, wird meistens das Pumping-Lemma für reguläre Sprachen verwendet. In schwierigeren Fällen kann man mithilfe des Satzes von Myhill-Nerode zeigen, dass der Index der Relation R_L nicht endlich ist. Dann existieren unendlich viele Klassen von Wörtern, die durch geeignete Fortsetzungen unterschieden werden können, weshalb kein endlicher Automat für L ausreicht.
Beispiele und Abschlusseigenschaften
Die Sprache {aⁱbʲ | i,j ∈ ℕ} ist regulär. Sie enthält Wörter, die zunächst aus i Zeichen a und anschließend aus j Zeichen b bestehen. Auch jede endliche Sprache L über einem beliebigen Alphabet Σ mit |L| ∈ ℕ ist regulär; ein Beispiel ist {a, ab}. Die leere Menge ist ebenfalls eine reguläre Sprache. Außerdem sind alle kontextfreien Sprachen über einem unären Alphabet, also über einem Alphabet mit |Σ| = 1, regulär. Die Dyck-Sprachen sind dagegen nicht regulär.
Die Klasse der regulären Sprachen ist unter mehreren Operationen abgeschlossen. „Abgeschlossen“ bedeutet, dass die Anwendung der jeweiligen Operation auf reguläre Sprachen wieder eine reguläre Sprache ergibt:
• Sind L₁ und L₂ regulär, dann ist ihre Vereinigung L₁ ∪ L₂ regulär.
• Der Durchschnitt L₁ ∩ L₂ ist regulär.
• Das Komplement L̄ = Σ* ∖ L einer regulären Sprache L ist regulär.
• Die Konkatenation {uv | u ∈ L₁ ∧ v ∈ L₂} ist regulär. Dabei werden jeweils ein Wort aus L₁ und ein Wort aus L₂ hintereinandergefügt.
• Der Kleene-Stern L* ist regulär. Er umfasst die beliebig häufige Konkatenation von Wörtern aus L sowie das leere Wort.
• Auch die Differenz L₁ ∖ L₂ zweier regulärer Sprachen ist regulär.
Entscheidbare Fragen
Für gegebene reguläre Sprachen L, L₁ und L₂ über einem Alphabet Σ treten mehrere typische Entscheidungsprobleme auf:
• Wortproblem: Gehört ein gegebenes Wort w ∈ Σ* zur Sprache L?
• Leerheitsproblem: Ist L = ∅?
• Schnittproblem: Ist L₁ ∩ L₂ = ∅?
• Endlichkeitsproblem: Besteht L aus einer endlichen Menge von Wörtern?
• Äquivalenzproblem: Gilt L₁ = L₂?
• Inklusionsproblem: Gilt L₁ ⊆ L₂?
Alle diese Probleme sind entscheidbar. Das bedeutet, dass es für jedes von ihnen ein Verfahren gibt, das für jede zulässige Eingabe nach endlich vielen Schritten eine korrekte Ja-oder-Nein-Antwort liefert.
