Reguläre Grammatik
In diesem Beitrag findest du alle wichtigen Informationen zur Regulären Grammatik in der theoretischen Informatik. Gestartet wird mit der Definition der formalen Grammatik vom Typ 3 und deren Produktionsregeln. Im Anschluss folgt ein ausführliches „Reguläre Grammatik Beispiel“, indem der Nachweis der regulären Sprache erläutert wird. Zum Abschluss wird dir der Zusammenhang mit endlichen Automaten erklärt.
Wenn du das Thema aber kurz und kompakt erklärt haben möchtest, schau dir einfach unser Video an. Dort wird dir die reguläre Grammatik anhand von Beispielen einfach und schnell erklärt!
Inhaltsübersicht
Reguläre Grammatik – Allgemein
Die Reguläre Grammatik stellt eine Typ 3 Grammatik der Chomsky-Hierarchie dar und erzeugt reguläre Sprachen. Es ist ein 4-Tupel, bestehend aus der Menge der Terminalsymbole, der Nichtterminale und der Produktionen, sowie einem Startsymbol.
Definition
Die Grammatik wird über dieses 4-Tupel erzeugt:
N ist dabei die Menge der Nichtterminale oder auch Variablen und wird mit Großbuchstaben bezeichnet.
T ist die Menge der Terminalsymbole in Kleinbuchstaben.
S ist das Startsymbol und als Variable in N enthalten.
P ist schließlich die Menge der Produktionsregeln.
Die Definition beschreibt somit zum einen die Grundelemente der Sprache, also Terminalsymbole, die beispielsweise bei Programmiersprachen für Schlüsselworte stehen. Aus diesen können dann Sätze zusammengestellt werden, die auf Produktionsregeln, bzw. Konstruktionsregeln basieren.
Produktionsregeln
Reguläre Grammatiken bestehen aus stark eingeschränkten Regeln der folgenden Form:
und 
Dabei unterscheidet man je nachdem, ob sich das Nonterminal auf 
entweder ganz links, oder ganz rechts befindet. Je nach Form wird deshalb zwischen rechtslinear oder linkslinear unterschieden.
Dabei darf auf der jeweiligen Seite immer nur eine Variable stehen.
Diese wird durch eine von drei Möglichkeiten auf der jeweiligen Seite ersetzt:
- Durch
– also nichts; - durch ein Terminalsymbol, also ein Zeichen aus dem Alphabet der Sprache;
- oder durch ein Terminalsymbol gefolgt von einem Nichtterminal.
Rechtslinear:
Linkslinear:
Dabei gilt, dass linkslineare und rechtslineare Grammatiken äquivalent sind, was bedeutet, dass zu jeder linkslinearen Grammatik eine rechtslineare Grammatik gibt, die die gleiche Sprache erzeugen und auch umgekehrt.
Reguläre Grammatiken und Reguläre Sprachen
Reguläre Grammatiken erzeugen reguläre Sprachen, deshalb gibt es für jede reguläre Sprache immer mindestens eine reguläre Grammatik.
Zur besseren Verständlichkeit betrachten wir die folgende Sprache als „Reguläre Grammatik Beispiel“:
Sie enthält alle Wörter, die mit einem bis n Nullen beginnen und mit keiner oder einer geraden Anzahl Einsen enden.
Wenn man diese Sprache auf eine wie eben beschriebene reguläre Grammatik zurückführen kann, dann ist sie regulär.
Reguläre Grammatik Beispiel
Gestartet wird mit dem Startsymbol S. Dabei wird versucht zunächst das kleinstmögliche Wort zu bilden. Das wäre einfach Null.
Mit der ersten Produktionsregel „S wird umgewandelt in Null“ bekommt man genau dieses Wort.
Man benötigt aber eine Möglichkeit mehr als eine 0 zu erzeugen. Das gelingt, indem an die Null einfach erneut das Startsymbol angefügt wird:
Nachdem eine Null erzeugt wird, befindet man sich wieder in S und kann dadurch so viele beliebige Nullen erschaffen. Im nächsten Schritt muss man das Wort entweder beenden oder mit den Einsen anfangen. Dabei kann man die Produktionsregel einfach erweitern:
S wird umgewandelt in Null S oder 1 S oder Epsilon.
Doch Vorsicht! Mit dieser Regel kann man das leere Wort 
erzeugen. Oder eines, das direkt mit einer 1 beginnt: 
. Beides darf in dieser Sprache aber nicht passieren. Deshalb muss zwischen dem Teil des Wortes, das Nullen enthält und dem Rest unterschieden werden. Dafür braucht man eine weitere Variable.
Mit dieser Regel können viele Nullen erschafft werden, dabei muss aber mindestens eine erzeugt werden, bevor man sich dem nächsten Teil des Wortes in B widmen kann. Von B aus beendet man entweder mit Epsilon oder erzeugt Einsen.
Wenn das Wort Einsen besitzt, müssen diese in gerader Anzahl vorhanden sein. Dies wird mit einer Schleife erreicht:
Dabei gelangt man von B mit einer 1 nach C und von dort mit einer weiteren 1 nach B zurück. Die Produktionsregeln erzeugen nun die beschriebene Sprache.
Wortproblem
Mit ihnen kann man nun auch überprüfen, ob ein Wort in der Sprache enthalten ist. Getestet wird mit „0“ „0“
Man wählt von 
aus zuerst 
und gehen dann direkt mit 
in den Endzustand. Das Wort ist also in der Sprache enthalten.
Wie sieht es mit „0“ „1“ aus? Gestartet wird bei S und geht dann über von 0 nach B.
Von hier aus wird eine 1 erzeugt und man landet in C.
Da man nicht in einem Endzustand ist, ist folglich „0“ “1“ nicht in der Sprache enthalten.
Beziehung deterministischer endlicher Automat
Zum einen gibt es für jede reguläre Grammatik einen deterministischen Automaten. Dieser wird durch einen nichtdeterministischen endlichen Automaten erstellt, indem aus den Nichtterminalsymbolen ein Zustand erstellt wird und zusätzlich aus jeder Konstruktionsregel einen Übergang erzeugt. Der nichtdeterministische Automat kann dann in einen deterministischen endlichen Automaten umgewandelt werden.
Im Gegenzug gibt es natürlich auch in jedem deterministischem endlichen Automaten eine reguläre Grammatik.
Allgemein gilt: Jede Sprache, die endliche Automaten akzeptieren, wird von einer regulären Grammatik erzeugt.
Wie du diese in endliche Automaten überführen kannst, erfährst du in unserem Video zu reguläre Sprachen .