Formale Grammatik

Definition

Eine formale Grammatik besteht aus einer endlichen Menge von Terminal-Symbolen (im folgenden kurz Terminale genannt), einer endlichen Menge von Nichtterminal-Symbolen (im folgenden kurz Nichtterminale genannt), einer endlichen Menge von Produktions-Regeln (im folgenden kurz Regeln genannt) und einem Startsymbol, welches zu den Nichtterminalen gehört.

Eine Regel besteht aus einer linken und einer rechten Seite, die jeweils ein Wort bestehend aus Terminalen und Nichtterminalen sind. Die rechte Seite kann dabei im Gegensatz zur lniken Seite auch das leere Wort (im folgenden mit $\epsilon$ symbolisiert) sein, also das Wort, welches keine Symbole enthält. Eine Regel kann auf ein Wort, bestehend aus Terminalen und Nichtterminalen, angewendet werden, wobei ein beliebigen Vorkommen der linken Seite der Regel im Wort durch die rechten Seite der Regel ersetzt wird. Eine Ableitung ist dann eine Folge von solchen Anwendungen der Regeln. Die Grammatik definiert dann eine formale Sprache, die aus allen Wörtern besteht, die nur aus Terminalen bestehen und vom Startsymbol abgeleitet werden können.

Nichtterminale werdem gewöhnlich durch Großbuchstaben, Terminale durch Kleinbuchstaben repräsentiert. Das Startsymbol wird meistens durch das $S$ repräsentiert.

Beispiel

Wir betrachten die Grammatik mit den Terminalen $\{a,b\}$, den Nichtterminalen $\{S,A,B\}$ und den Regeln

$S\rightarrow ABS$

$S\rightarrow \epsilon$ (wobei $\epsilon$; das leere Wort ist)

$BA\rightarrow AB$

$BS\rightarrow b$

$Bb\rightarrow bb$

$Ab\rightarrow ab$

$Aa\rightarrow aa$

und dem Startsymbol $S$, definiert die Sprache aller Wörter der Form $a^{n}b^{n}$, d.h. $n$ Kopien von $a$ gefolgt von $n$ Kopien von $b$.

Man klassifiziert verschiedene Typen von Grammtiken in der sogenannten Chomsky-Hierarchie.