Reguläre Grammatik

Eine reguläre Grammatik ist in der Informatik eine formale Grammatik vom Typ 3 der Chomsky-Hierarchie. Die von solchen Grammatiken erzeugten Sprachen heißen reguläre Sprachen.

Definition

Eine reguläre Grammatik $G=\left(V,T,P,S\right)$ (mit Vokabular $V$, Terminalalphabet $T$, Menge der Nichtterminalen (Variablen) $N:=V\setminus T$, Produktionsregeln $P$ und Startsymbol $S\in N$) ist eine kontextfreie Grammatik, deren Produktionsregeln bestimmten weiteren Einschränkungen genügen. Es gibt zwei verschiedene Arten von Einschränkungen, die dann spezifisch rechtsreguläre bzw. linksreguläre Grammatiken definieren. Da man sich aus praktischen Gründen bei Anwendungen meist an die rechtsregulären Grammatiken hält, sagt man oft auch kurz „regulär“, wo man eigentlich „rechtsregulär“ meint (ansonsten kann regulär linksregulär oder rechtsregulär bedeuten).

Für Produktionsregeln $w_{1}\to w_{2}\in P$ regulärer Grammatiken darf die linke Seite immer nur ein Nichtterminalsymbol sein, $w_{1}\in N$. Damit ist jede reguläre Grammatik auch kontextfrei. Außerdem darf die rechte Seite jeder Regel ein oder mehrere Terminal- und höchstens ein Nichtterminalsymbol enthalten. Alle Regeln mit zwei Symbolen auf ihrer rechten Seite müssen die gleiche Reihenfolge von Terminal- und Nichtterminalsymbol einhalten.

Rechtsreguläre Grammatiken

Bei rechtsregulären Grammatiken darf die rechte Seite $w_{2}$ einer Produktion $w_{1}\to w_{2}$ nur das leere Wort, ein oder mehrere Terminalsymbole oder ein oder mehrere Terminale gefolgt von einem einzigen Nichtterminal sein. Ableitungen in solchen Grammatiken wachsen also am rechten Ende einer Satzform.

Formal kann man die Bedingung an die Produktionsmenge $P$ einer rechtsregulären Grammatik $G$ so ausdrücken:

$\forall \left(w_{1}\to w_{2}\right)\in P:\left(w_{1}=S\land w_{2}=\varepsilon \right)\lor \left(w_{1}\in N\land w_{2}\in T^{+}\cup T^{+}N\right)$

$\varepsilon$ steht dabei für das leere Wort. Dies ist gleichbedeutend mit

$P\subset \{(S,\varepsilon )\}\cup N\times (T^{+}\cup T^{+}N)$.

Man beachte, dass die scheinbar strengere Anforderung

$P\subset \{(S,\varepsilon )\}\cup N\times (T\cup TN)$

gleichmächtig ist, d. h. dieselbe formale Sprache erzeugt. Man muss nur mit Hilfe zusätzlicher Nichtterminalzeichen mehrere Regeln der Art $A\to bB$ (mit Terminalzeichen $b$ und Nichtterminalen $A,B$) hintereinander ausführen, um zu $A\rightsquigarrow wB$ und schließlich auch zu $A\rightsquigarrow w$ mit einem nichtleeren Wort aus Terminalzeichen $w$ zu gelangen.

Linksreguläre Grammatiken

Bei linksregulären Grammatiken darf umgekehrt die rechte Seite $w_{2}$ einer Produktion nur das leere Wort, ein Terminalsymbol oder ein Nichtterminal gefolgt von einem Terminal sein. Hier verlängern also die Ableitungen die Satzformen linksseitig.

Formal sehen die Bedingungen folgendermaßen aus:

$\forall \left(w_{1}\to w_{2}\right)\in P:\left(w_{1}\in N\right)\land \left(w_{2}\in \{\varepsilon \}\cup T^{*}\cup NT^{*}\right)$

Erweiterte reguläre Grammatiken

Eine erweiterte rechtsreguläre Grammatik folgt diesen Regeln:

1. B → a – wobei B ein Nichtterminal aus N ist, und a ein Terminal aus Σ.
2. A → B – wobei A und B Nichtterminale aus N sind.
3. A → wB – wobei A und B aus N und w aus Σ^* ist.
4. A → ε – wobei A aus N ist und ε das leere Wort.

Erweiterte linksreguläre Grammatiken sind analog zu erweiterten rechtsregulären Grammatiken.

Erweiterte reguläre Grammatiken sind gleichmächtig den streng regulären Grammatiken, d. h., sie können ebenfalls genau alle regulären Sprachen erzeugen.

Weitere Schreibweisen

Die Bedingung für reguläre Grammatiken lässt sich auch kürzer notieren, indem man die Menge der gültigen Produktionsregeln definiert:

$P\subseteq N\times (\{\varepsilon \}\cup T\cup TN)$ (rechtsregulärer Fall)

$P\subseteq N\times (\{\varepsilon \}\cup T\cup NT)$ (linksregulärer Fall)

Für beliebige $X,Y\in N$ und $a\in T$ sind also im rechtsregulären Fall nur folgende Muster von Regeln erlaubt:

1. $X\to aY$
2. $X\to a$
3. $X\to \varepsilon$

Für linksreguläre Grammatiken tritt anstelle des erstgenannten Musters das folgende ein:

1. $X\to Ya$

Die jeweils erste Produktion ist rechts- beziehungsweise linksregulär (auch rechts- und linkslinear genannt). Eine reguläre Grammatik darf nicht Regeln nach beiden Mustern für 1. mischen.

Reguläre Sprachen

Eine von einer regulären Grammatik erzeugte Sprache nennt man reguläre Sprache. Für jede reguläre Sprache existiert auch immer mindestens eine reguläre Grammatik.

Die regulären Sprachen erweisen sich als abgeschlossen unter Komplementbildung, Konkatenation, Schnitt, Vereinigung und Bildung des Kleeneschen Abschlusses.

Jede reguläre Sprache wird auch von einem geeigneten deterministischen – und dann notwendigerweise auch von einem nichtdeterministischen – endlichen Automaten akzeptiert und von einem geeigneten regulären Ausdruck beschrieben. Umgekehrt werden die Sprachen, die ein deterministischer oder nichtdeterministischer endlicher Automat akzeptiert bzw. die ein regulärer Ausdruck beschreibt, auch von einer geeigneten regulären Grammatik erzeugt. Dass in den regulären Sprachen die durch vier verschiedene Formalismen definierten Sprachklassen in einer Klasse zusammenfallen, bringt ihnen ihre große Bedeutung ein.

Auch die Klassen der rechtsregulären und der linksregulären Grammatiken fallen zusammen: Zu jeder linksregulären Grammatik gibt es eine rechtsreguläre Grammatik, die dieselbe Sprache erzeugt, und umgekehrt.

Beschreibung des Ableitungsvorgangs

Verfolgt man den Verlauf einer Ableitung in einer rechtsregulären Grammatik, so bestehen alle Satzformen, die überhaupt noch ein Nichtterminalsymbol besitzen, aus einem Wort aus Terminalen vorneweg, gefolgt von einem einzigen Nichtterminal. Das abgeleitete Wort entsteht also schrittweise durch Anfügen eines Terminalsymbols auf der rechten Seite des initialen Terminalworts und gleichzeitiger Änderung des finalen Nichtterminals.

Ein deterministischer Automat, der $L_{doremi}$ erkennt

Die folgende rechtsreguläre Beispielgrammatik mit $Ta=\{d,e,i,m,o,r\}$ beschreibt die Sprache $L_{doremi}=\{do,re,mi\}^{*}$.

$G_{doremi}=(\{S,A,B,C\},T,P,S)$ mit folgenden Regeln in $P$:

$S\to dA|rB|mC|\varepsilon$

$A\to oS$

$B\to eS$

$C\to iS$

Das Wort $domire\in L_{doremi}$ hat folgende Ableitung:

$S\rightsquigarrow dA\rightsquigarrow \ doS\rightsquigarrow \ domC\rightsquigarrow \ domiS\rightsquigarrow \ domirB\rightsquigarrow \ domireS\rightsquigarrow \ domire$

Dieser Prozess entspricht dem Einlesen des Wortes in einem endlichen Automaten. Es gibt einen entsprechenden Automaten, dessen Nichtterminalsymbole den Zuständen entsprechen und in dem es für jede Regel $X\to aY$ eine Transition $(X,a,Y)$ im Automaten gibt. Der Automat zur Beispielgrammatik ist im Bild dargestellt.