Reguläre Grammatik

Grundidee und Definition

Eine reguläre Grammatik ist eine formale Grammatik vom Typ 3 der Chomsky-Hierarchie. Die von ihr erzeugten Sprachen heißen reguläre Sprachen. Sie ist eine besondere kontextfreie Grammatik mit zusätzlichen Einschränkungen für die Produktionsregeln.

Eine reguläre Grammatik wird als G = (V, T, P, S) beschrieben. Dabei ist V das Vokabular, T das Terminalalphabet, N := V \ T die Menge der Nichtterminale (Variablen), P die Menge der Produktionsregeln und S ∈ N das Startsymbol. Jede linke Regelseite darf ausschließlich aus einem Nichtterminalsymbol bestehen: Für w₁ → w₂ ∈ P gilt w₁ ∈ N. Deshalb ist jede reguläre Grammatik auch kontextfrei.

Auf der rechten Seite einer Regel dürfen ein oder mehrere Terminalsymbole und höchstens ein Nichtterminalsymbol stehen. Regeln mit zwei Symbolen müssen dabei immer dieselbe Reihenfolge von Terminal- und Nichtterminalsymbol einhalten. Je nach dieser Reihenfolge unterscheidet man rechtsreguläre und linksreguläre Grammatiken. In der Praxis meint „regulär“ häufig verkürzt „rechtsregulär“, obwohl der Begriff grundsätzlich beide Varianten umfasst.

Rechtsreguläre Grammatiken

Bei einer rechtsregulären Grammatik darf die rechte Seite w₂ einer Produktion w₁ → w₂ nur aus dem leeren Wort, aus einem oder mehreren Terminalen oder aus mehreren Terminalen gefolgt von genau einem Nichtterminal bestehen. Die Ableitungen wachsen damit am rechten Ende einer Satzform.

Formal gilt für jede Regel:

∀(w₁ → w₂) ∈ P: (w₁ = S ∧ w₂ = ε) ∨ (w₁ ∈ N ∧ w₂ ∈ T⁺ ∪ T⁺N).

Dabei bezeichnet ε das leere Wort. Gleichbedeutend ist:

P ⊆ {(S, ε)} ∪ N × (T⁺ ∪ T⁺N).

Die scheinbar strengere Einschränkung

P ⊆ {(S, ε)} ∪ N × (T ∪ TN)

ist gleichmächtig. Sie erzeugt also dieselben formalen Sprachen. Mehrere Terminale können durch zusätzliche Nichtterminale schrittweise erzeugt werden. Aus Regeln der Form A → bB entstehen so Ableitungen A ⇝ wB und schließlich A ⇝ w, wobei w ein nichtleeres Wort aus Terminalzeichen ist.

Linksreguläre Grammatiken

Bei einer linksregulären Grammatik ist die Reihenfolge umgekehrt. Die rechte Seite darf nur das leere Wort, ein Terminalsymbol oder ein Nichtterminal gefolgt von einem Terminal sein. Die Satzformen werden somit linksseitig verlängert.

Die formale Bedingung lautet:

∀(w₁ → w₂) ∈ P: (w₁ ∈ N) ∧ (w₂ ∈ {ε} ∪ T* ∪ NT*).

Rechts- und linksreguläre Grammatiken unterscheiden sich daher in der Position des Nichtterminals. Beide Klassen sind jedoch gleich mächtig: Zu jeder linksregulären Grammatik gibt es eine rechtsreguläre Grammatik mit derselben erzeugten Sprache und umgekehrt. Die beiden Regeltypen dürfen in einer regulären Grammatik nicht vermischt werden.

Erweiterte Formen und Regelmuster

Erweiterte rechtsreguläre Grammatiken erlauben folgende Regeltypen:

• B → a, wobei B ein Nichtterminal aus N und a ein Terminal aus Σ ist.
• A → B, wobei A und B Nichtterminale aus N sind.
• A → wB, wobei A und B aus N und w aus Σ* ist.
• A → ε, wobei A aus N ist und ε das leere Wort bezeichnet.

Erweiterte linksreguläre Grammatiken sind dazu analog. Erweiterte reguläre Grammatiken sind gleichmächtig mit streng regulären Grammatiken und können daher ebenfalls genau alle regulären Sprachen erzeugen.

Die zulässigen Regeln lassen sich kürzer angeben. Im rechtsregulären Fall gilt:

P ⊆ N × ({ε} ∪ T ∪ TN).

Damit sind für X, Y ∈ N und a ∈ T die Muster X → aY, X → a und X → ε erlaubt. Im linksregulären Fall gilt:

P ⊆ N × ({ε} ∪ T ∪ NT).

Dort ersetzt X → aY das Muster X → Ya. Die jeweils erste Form heißt auch rechtslinear beziehungsweise linkslinear.

Reguläre Sprachen und gleichwertige Modelle

Eine von einer regulären Grammatik erzeugte Sprache heißt reguläre Sprache. Für jede reguläre Sprache existiert mindestens eine reguläre Grammatik. Reguläre Sprachen sind abgeschlossen unter Komplementbildung, Konkatenation, Schnitt, Vereinigung und Bildung des Kleeneschen Abschlusses.

Dieselben Sprachen können durch verschiedene Formalismen beschrieben werden. Jede reguläre Sprache wird von einem geeigneten deterministischen endlichen Automaten akzeptiert und damit notwendigerweise auch von einem nichtdeterministischen endlichen Automaten. Außerdem lässt sie sich durch einen geeigneten regulären Ausdruck beschreiben. Umgekehrt erzeugen reguläre Grammatiken genau die Sprachen, die von deterministischen oder nichtdeterministischen endlichen Automaten akzeptiert beziehungsweise von regulären Ausdrücken beschrieben werden. Dass diese vier Formalismen dieselbe Sprachklasse festlegen, erklärt die große Bedeutung regulärer Sprachen.

Ableitung und Beispiel

Bei einer Ableitung in einer rechtsregulären Grammatik bestehen alle Satzformen, die noch ein Nichtterminal enthalten, aus einem vorderen Wort aus Terminalen und genau einem abschließenden Nichtterminal. In jedem Schritt wird ein Terminal angefügt und das letzte Nichtterminal durch ein neues Nichtterminal oder durch das Ende der Ableitung ersetzt.

Die Beispielgrammatik G_doremi = ({S, A, B, C}, T, P, S) mit Tₐ = {d, e, i, m, o, r} erzeugt die Sprache L_doremi = {do, re, mi}*. Ihre Regeln sind:

• S → dA | rB | mC | ε
• A → oS
• B → eS
• C → iS

Für das Wort domire ∈ L_doremi ergibt sich die Ableitung:

S ⇝ dA ⇝ doS ⇝ domC ⇝ domiS ⇝ domirB ⇝ domireS ⇝ domire.

Die Grammatik arbeitet dabei wie ein endlicher Automat. Die Nichtterminale entsprechen Zuständen. Für jede Regel X → aY gibt es eine Transition (X, a, Y). Das Lesen eines Terminalsymbols führt also vom Zustand X in den Zustand Y; die Regel X → ε entspricht dem erfolgreichen Abschluss der Worterzeugung.