Formale Grammatiken

Durch Formale Grammatiken können formale Sprachen beschrieben und erzeugt werden können. Sie werden in der theoretischen Informatik, insbesondere in der Berechenbarkeitstheorie, und im Compilerbau angewandt. Formale Grammatiken werden in der Chomsky-Hierarchie klassifiziert.

Beschreibung

Mit einer formalen Grammatik lassen sich ausgehend von einem Startsymbol SS (auch Startvariable genannt) Produktionsregeln aus einer Regelmenge PP anwenden, um neue Zeichenfolgen zu erzeugen, welche wiederum weiter ersetzt werden können. Diesen Vorgang nennt man auch Ableitung.
Ebenso wie auf eine gegebene Zeichenfolge mehrere Regeln gleichzeitig anwendbar sein können, muss es nicht immer nur eine Stelle in der Zeichenfolge geben, auf die eine Regel passt. Formale Grammatiken schreiben keine Reihenfolge vor. Alle nur aus Terminalsymbolen bestehenden Wörter, die sich aus dem Startsymbol ableiten lassen, zählen zur von der Grammatik beschriebenen Sprache.
 
 

Definition

Eine formale Grammatik ist ein 4-Tupel G=(V,Σ,P,S)G = (V, \Sigma, P, S) bestehend aus:
  • VV, einer endlichen Menge, welche als Vokabular bezeichnet wird,
  • Σ⊂V\Sigma \subset V, einer Teilmenge von VV, die Alphabet genannt wird und deren Elemente Terminalsymbole heißen,
  • P⊂(V∗∖Σ∗)×V∗P \subset \left( V^* \setminus \Sigma^* \right) \times V^*, einer endlichen Menge von Produktionsregeln, sowie
  • S∈V∖ΣS\in V\setminus \Sigma, dem Startsymbol.
Hierbei bezeichnet X∗X^* die Kleenesche Hülle von XX.
Die Menge N=V∖ΣN = V\setminus \Sigma ist die Menge von Nichtterminalsymbolen oder auch Metasymbolen.
Eine formale Grammatik GG kann auch als das Tupel (N,Σ,P,S)(N, \Sigma, P, S) angegeben werden.

Ableitung

Eine Regel R→Q∈PR\rightarrow Q \in P einer gegebenen Grammatik GG besagt, dass in einem Wort w∈V∗w \in V^\ast mit RR als Infix, dieses durch das Wort QQ ersetzt werden kann, so dass ein neues Wort w′w^\prime mit QQ als Infix entsteht. Man spricht hierbei auch davon, dass ww in w′w^\prime mit der Grammatik GG bzw. durch die Regel R→QR \rightarrow Q übergeht, oder auch, dass w′w^\prime aus ww abgeleitet wurde. Dies kann durch w↦R→Qw′w \mapto_{R \rightarrow Q} w^\prime notiert werden (häufig auch ⇒\Rightarrow anstatt ↦\mapto). Soll nur ausgedrückt werden, dass in der Grammatik GG das Wort w′w^\prime aus ww entstehen kann, ohne eine Regel zu benennen, schreibt man statt dessen w↦Gw′w \mapto_G w^\prime (ist die Grammatik aus dem Kontext offensichtlich, auch einfach w↦w′w \mapto w^\prime). Demnach ist ein solcher Übergang von ww in w′w^\prime eine Transitionsrelation, die eine natürliche Erweiterung von PP auf alle möglichen V∗V^*-Kontexte darstellt, nämlich:
↦  :=  {(u∘R∘v,u∘Q∘v)∣(R,Q)∈P,u,v∈V∗}\mapto\;:=\;\{(u \circ R \circ v, u \circ Q \circ v) | (R,Q)\in P, u,v\in V^*\}.
Gibt es nun eine Folge von Wörtern w0,w1,…,wn∈V∗w_0, w_1, \ldots, w_n \in V^\ast, bei der gilt, dass für jede natürliche Zahl ii mit 0≤i<n0 \le i < n das Wort wiw_i in wi+1w_{i+1} übergeht (wi↦Gwi+1)(w_i \mapto_G w_{i+1}), so ist wnw_n in nn Schritten aus w0w_0 ableitbar, was durch w0↦Gnwnw_0 \mapto_G^n w_n dargestellt wird. Eine solche Wortfolge w0,w1,…,wnw_0, w_1, \ldots, w_n wird Ableitung oder Rechnung von w0w_0 in wnw_n der Länge nn genannt. Weiterhin heißt ww in w′w^\prime ableitbar, wenn es mindestens ein n∈N0n \in \mathbb{N}_0 gibt, so dass w′w^\prime in nn Schritten aus ww ableitbar ist. Wenn ww in w′w^\prime ableitbar ist, so wird dies durch die Schreibweise w↦G∗w′w \mapto_G^\ast w^\prime dargestellt. Dabei wird zusätzlich definiert, dass für jedes Wort w∈V∗w \in V^\ast gilt, dass w↦G∗ww \mapto_G^\ast w ist, so dass die Relation ↦G∗\mapto_G^\ast die reflexiv-transitive Hülle der Relation ↦G\mapto_G ist.

Die von einer Grammatik erzeugte Sprache

Die von der Grammatik GG erzeugte formale Sprache L(G)L(G) ist genau diejenige Sprache, die aus allen Wörtern besteht, die zum einen nur aus Terminalsymbolen bestehen und die zum anderen vom Startsymbol mit einer endlichen Anzahl von Schritten abgeleitet werden können:
L(G):={w∈Σ∗∣S↦G∗w}L ( G ) := \left\{ w \in \Sigma^* | S \mapto_G^* w \right\}
Dabei ist es egal, in welcher Reihenfolge die Produktionsregeln auf die abgeleiteten Wörter angewandt werden, oder ob es mehrere Möglichkeiten gibt, um ein Wort ww aus SS abzuleiten. Zwei Grammatiken G1G_1 und G2G_2 sind genau dann äquivalent, wenn die durch G1G_1 und G2G_2 erzeugten Sprachen gleich sind:
G1G_1 ist äquivalent zu G2:⟺L(G1)=L(G2) G_2: \Longleftrightarrow L(G_1) = L(G_2).

Beispiele

G1G_1 sei eine Grammatik mit den Terminalsymbolen {a,b}\{a, b\}, den Nichtterminalsymbolen {S,A,B}\{S, A, B\}, dem Startsymbol SS und mit den Regeln
S→ABS (1)S→ε (2)BA→AB (3)BS→b (4)Bb→bb (5)Ab→ab (6)Aa→aa (7) \begin{matrix} S&\to&ABS&\,(1)\\ S&\to&\varepsilon&\,(2)\\ BA&\to&AB&\,(3)\\ BS&\to&b&\,(4)\\ Bb&\to&bb&\,(5)\\ Ab&\to&ab&\,(6)\\ Aa&\to&aa&\,(7) \end{matrix}
Dabei ist ε\varepsilon das leere Wort, welches ein Wort der Länge 0 ist. Diese Grammatik G1G_1 definiert die Sprache aller Wörter der Form anbna^n b^n mit n∈N0n \in \mathbb N_0. So sind auf Grund der folgenden Ableitungen die Wörter ε, ab\varepsilon,\, ab und aabbaabb Elemente der durch G1G_1 beschriebenen Sprache:
  • S↦εS\mapto\varepsilon, mittels Regel (2),
  • S↦ABS↦Ab↦abS\mapto ABS\mapto Ab\mapto ab, mittels der Regeln (1), (4) und (6),
  • S↦ABS↦ABABS↦ABAb↦AABb↦AAbb↦Aabb↦aabbS\mapto ABS\mapto ABABS\mapto ABAb\mapto AABb\mapto AAbb\mapto Aabb\mapto aabb, mittels der Regeln (1),(1),(4),(3), (5), (6) und (7).
Es gibt aber noch andere Möglichkeiten, um das Wort aabbaabb aus SS abzuleiten.
Eine weitere Grammatik, die dieselbe Sprache beschreibt, ist die kontextfreie Grammatik G2G_2 mit den Regeln: S→aSb ∣ ε\begin{matrix}S&\to&aSb\ |\ \varepsilon\end{matrix}
Jede rekursiv aufzählbare Sprache wird von mehreren (und zwar abzählbar unendlich vielen) Grammatiken erzeugt. Allerdings gibt es auch Sprachen, die sich von keiner Grammatik erzeugen lassen.

Klassen von Grammatiken

Grammatiken werden Klassen zugeordnet, die sich durch Gemeinsamkeiten auszeichnen. Die bekannteste Klassifikation beschrieben Noam Chomsky und Marcel Schützenberger mit der Chomsky-Hierarchie.

Weitere Sprachklassen

Von der Chomsky-Hierarchie abgesehen haben sich weitere Klassen an Grammatiken etabliert:
  • Monotone Grammatiken beschreiben die gleiche Sprachklasse wie die kontextsensitiven Grammatiken. Etwas strenger sind die wachsend kontextsensitiven Grammatiken, die eine Teilklasse der kontextsensitiven Sprachklasse beschreiben.
  • Deterministisch kontextfreie Grammatiken beschreiben die deterministisch kontextfreien Sprachen. Sie werden auch durch die LR(k)-Grammatiken beschrieben, welche für den Compilerbau von Bedeutung sind. Andere im Compilerbau bekannte Grammatiken sind LL(k)-Grammatiken und LF(k)-Grammatiken.

Das ist ein Mittel, das Paradies nicht zu verfehlen: auf der einen Seite einen Mathematiker, auf der anderen einen Jesuiten; mit dieser Begleitung muß man seinen Weg machen, oder man macht ihn niemals.

Friedrich der Große

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Formale Grammatik aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Theoretische Informatik