Reguläre Grammatik
Einführung
Eine formale Sprache lässt sich einfach durch Aufzählung aller ihrer Wörter angeben. Um eine Sprache angeben zu können, benötigt man eine endliche Beschreibung der Sprache. Eine solche existiert nur, wenn alle Wörter der Sprache einem bestimmten Bildungsgesetz folgen (z.B. "alle Wörter, die mit a anfangen, mindestens fünf b's und genauso viele c's enthalten und mit a oder c aufhören") (Quelle: http://www.iti.fh-flensburg.de).
In der Theorie der formalen Sprachen werden Grammatiken zur Beschreibung von Sprachen verwendet. Mithilfe einer Grammatik lassen sich die Wörter einer Sprache L erzeugen: Ein Wort gehört zu L, wenn es sich durch eine Folge von bestimmten zulässigen Ersetzungen aus einem sogenannten Startsymbol erzeugen lässt.
Reguläre Grammatiken sind ein Spezialfall von kontextfreien Grammatiken.
Definition
Eine Grammatik ist ein 4-Tupel: G = (V, T, P, S).
Hierfür gilt:
V: Alphabet der Variablen oder Nicht-Terminalzeichen.
T: Alphabet der Terminalzeichen, das sind die Grundelemente der Sprache.
P: Die Elemente von P heißen Produktionen auch Ersetzungsregeln oder Ableitungsregeln genannt.
S: Element von V ist eine spezielle Variable, das Startsymbol.
Die Terminalsymbole T sind die Grundelemente der Sprache. Bei Programmiersprachen sind das z.B. die Schlüsselworte wie Begin, End oder die arithmetischen Operatoren. Aus Terminalsymbolen können entsprechend den Konstruktionsregeln Sätze zusammengestellt werden. Die Konstruktionsregeln werden in Verbindung mit Grammatiken als Produktionen bezeichnet, da diese angeben, dass aus der linken Seite der Produktion die rechte Seite hergeleitet werden kann. Die erste Produktion definiert immer den Ausgangspunkt von der Startvariablen S.
Beispiel
Eine reguläre Sprache kann man also auch anstatt durch einen regulären Ausdruck durch eine reguläre Grammatik beschreiben! Betrachten wir folgendes einfaches Beispiel:
Das Alphabet sei {a, b}, die Sprache sei durch ab(bb)*a beschrieben. Die Sprache ist demnach {aba, abbba, abbbbba…}, jedes Wort besteht aus einem a und danach einer ungeraden Zahl an b’s, gefolgt von einem schließenden a.
V= {S,A,B,C}
T={a,b}
P={
1. S => aA
2. A => bB
3. B => a
4. B => bC
5. C => bB}
S ist der Startpunkt, Großbuchstaben sind hier sogenannte Nichtterminale (also quasi Namen von weiteren Ableitungsregeln), Kleinbuchstaben sind Terminalzeichen (Zeichen des Alphabets, hier also nur a oder b). Man fängt bei S an. Alles, was links vom Pfeil steht, kann man durch das Ersetzen, was rechts davon steht. Regel 2 sagt also, dass man jedes irgendwo auftauchende A durch bB ersetzen kann. Eine Ableitung ist dann abgeschlossen, wenn sie nur noch aus Terminalzeichen, also Buchstaben des Alphabets, besteht (hier a und b).
aba entsteht durch die Regeln 1, 2, 3:
S => aA, => abB, => aba
abbba entsteht durch die Regeln 1, 2, 4, 5, 3:
S => aA, => abB, => abbC, => abbbB, => abbba
abbbbba entsteht durch die Regeln 1, 2, 4, 5, 4, 5, 3:
S => aA, => abB, => abbC, => abbbB, => abbbbC, =>abbbbbB, =>abbbbba
Eine (rechts-)reguläre Grammatik erfüllt folgende Bedingungen:
Links vom Pfeil steht immer nur ein einziges Nichtterminalzeichen.
Rechts vom Pfeil steht entweder gar nichts (dargestellt durch ein ε), oder genau ein Terminalzeichen, oder genau ein Terminal gefolgt von genau einem Nichtterminal.
Man sieht an der Ableitung der drei Wörter oben gut, das bei einer regulären Grammatik das Wort einzelner Buchstabe für einzelner Buchstabe von links nach rechts aufgebaut wird. Die Regeln für diesen Grammatiktyp sind so beschaffen, dass das immer so ist. Ein Wort, das 6 Zeichen lang ist, wird immer in 6 Schritten abgeleitet.
Rechtsreguläre Grammatik
Bei rechtsregulären (auch rechtslinear genannt) Grammatiken darf die rechte Seite einer Produktion x1 → x2 (hier also x2) 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.
Das oben dargestellten Beispiel beschreibt eine rechtsreguläre Grammatik .
V= {S,A,B,C}
T={a,b}
P={
1. S => aA
2. A => bB
3. B => a
4. B => bC
5. C => bB}
Linksreguläre Grammatik
Bei linksregulären Grammatiken (auch linkslinear genannt) darf umgekehrt die rechte Seite einer Produktion x1 → x2 (hier also x2) nur das leere Wort, ein Terminalsymbol oder ein Nichtterminal gefolgt von einem Terminal sein. Hier verlängern also die Ableitungen die Satzformen linksseitig.
Jede rechtsreguläre Grammatik lässt sich in eine linksreguläre Grammatik formulieren und umgekehrt.
V={S,A,B}
T={a,b}
P={
1. S => Aa
2. A => Bb
3. B => Ab
4. B => a}