Theoretische Informatik

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:

G=(N,\ T,\ P,\ S)

N ist dabei die Menge der Nichtterminale oder auch Variablen und wird mit Großbuchstaben bezeichnet.

N=\left\{B,C,\ D\right\}

T ist die Menge der Terminalsymbole in Kleinbuchstaben.

T=\left\{a,b,\ c\right\}

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:

A,B\ \in\ (V\ -\ \Sigma) und \alpha\ \in\ \Sigma

Dabei unterscheidet man je nachdem, ob sich das Nonterminal auf rS 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 \varepsilon – also nichts;
  • durch ein Terminalsymbol, also ein Zeichen aus dem Alphabet der Sprache;
  • oder durch ein Terminalsymbol gefolgt von einem Nichtterminal.
Reguläre Grammatik
direkt ins Video springen
Reguläre Grammatik

Rechtslinear:

A\ \rightarrow\ \alpha B
A\ \rightarrow\ \alpha

Linkslinear:

A\ \rightarrow\ B\alpha
A\ \rightarrow\ \alpha

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“:

L=\ \left\{0^n1^{2m}\ |\ n>0,\ m\geq0\right\}
\Sigma=\ \left\{0,1\right\}

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.

S\ \rightarrow0

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:

S\ \rightarrow0S

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\ \rightarrow0S\ \left|\ 1S\ \right|\ \varepsilon

S wird umgewandelt in Null S oder 1 S oder Epsilon.

Doch Vorsicht! Mit dieser Regel kann man das leere Wort  S\ \rightarrow\varepsilon erzeugen. Oder eines, das direkt mit einer 1 beginnt: (S\ \rightarrow1S). 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.

S\ \rightarrow0S\ |\ 0B

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.

B\ \rightarrow1B\ |\ \varepsilon

Wenn das Wort Einsen besitzt, müssen diese in gerader Anzahl vorhanden sein. Dies wird mit einer Schleife erreicht:

B\ \rightarrow1C\ |\ \varepsilon
C\ \rightarrow1B

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.

S\ \rightarrow0S\ |\ 0B
B\ \rightarrow1C\ |\ \varepsilon
C\ \rightarrow1B

Wortproblem

Mit ihnen kann man nun auch überprüfen, ob ein Wort in der Sprache enthalten ist. Getestet wird mit „0“ „0“

S\ \rightarrow0S
S\ \rightarrow0B
B\ \rightarrow\varepsilon

Man wählt von S aus zuerst 0S und gehen dann direkt mit 0B 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.

S\ \rightarrow0B

Von hier aus wird eine 1 erzeugt und man landet in C.

B\ \rightarrow1C

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 .

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.