Formale Grammatik

Formale Grammatiken sind mathematische Modelle von Grammatiken, die so genannte formale Sprachen erzeugen und besonders in der Theoretischen Informatik, insbesondere in der Berechenbarkeitstheorie und dem Compilerbau, Anwendung finden.

Grundlagen

Ein Text (Zeichenkette) ist eine Folge von Zeichen (Terminalsymbolen). In der Theorie sind Terminalsymbole häufig auf Kleinbuchstaben beschränkt, z.B.

aaaaabcc

, in der Praxis jedoch auch andere Symbole wie Satzzeichen und Schlüsselwörter von Programmiersprachen, z. B. FOR, IF, PROGRAM, usw.

Eine formale Grammatik erlaubt es, zu entscheiden, ob ein Text der Grammatik folgt, also ob er „gültig“ ist. Die Menge aller Texte, die der Grammatik folgen, nennt man die Sprache dieser Grammatik. Einen Text, der der Grammatik folgt, nennt man auch ein Wort dieser Sprache. Umgekehrt erlaubt es eine Grammatik auch, alle Wörter ihrer Sprache zu erzeugen.

Formale Grammatiken werden häufig als Semi-Thue-System angegeben (reguläre auch oft als Regulärer Ausdruck). Die gängigen Notationen verwenden Pseudosymbole, sogenannte Nichtterminalsymbole, die im Text nicht auftauchen (oft werden hierfür Großbuchstaben verwendet). Diese Symbole wirken wie Platzhalter, die aufgrund von Regeln (sog. Produktionsregeln oder Produktionen) durch andere Platzhalter oder Terminalsymbole oder eine beliebige Kombination von Platzhaltern und Terminalsymbolen ersetzt werden. Die Regeln produzieren aus einer Folge von Terminalsymbolen und Nichtterminalsymbolen andere Folgen. Beispiele für solche Regeln wären

$A \rightarrow a$
$A \rightarrow Aa$
$B \rightarrow Ab$
$C \rightarrow Bcc$

Ein Nichtterminalsymbol wird als Startsymbol definiert. Aufgrund der Regeln können dann gültige Texte produziert werden. Nimmt man $C$ als Startsymbol, so ergibt sich im Beispiel folgende Ableitung:

$C \rightarrow Bcc \rightarrow Abcc \rightarrow Aabcc \rightarrow Aaabcc \rightarrow ... \rightarrow aaa...aabcc$

Der obenstehende Text $aaaaabcc$ kann also durch sukzessive Anwendung der Regeln aus dem Startsymbol $C$ produziert werden. Die Regeln heißen daher auch Produktionsregeln oder Produktionen. Alle Texte, die so produziert werden können, sind gültig im Sinne der formalen Grammatik (also Wörter der Sprache, die die Grammatik definiert).

Gültige Texte wären hier $abcc, aabcc, aaabcc, ...$ , der Text $bcbca$ ist dagegen ungültig.

Definition

Eine formale Grammatik $G$ ist gegeben durch ein 4-Tupel, bestehend aus

einer endlichen Menge $N$ von Nichtterminalsymbolen (im Folgenden kurz Nichtterminale, oft aber auch Variablen genannt)
einer endlichen Menge $\Sigma$ von Terminalsymbolen (im Folgenden kurz Terminale genannt) (wobei das Alphabet $\Sigma$ und die Nichtterminale N disjunkt sind)
einer endlichen Menge $P$ von Produktionsregeln (im Folgenden kurz Regeln, oft auch Produktionen, genannt)
einem Startsymbol $S$ , welches zu den Nichtterminalen gehört.

Formal: $G = \left( N, \Sigma, P, S \right)$ , $S \in N$ , $N \cap \Sigma = \empty$

Nichtterminale werden gewöhnlich durch Großbuchstaben, Terminale durch Kleinbuchstaben repräsentiert.

Eine Regel besteht aus einer linken (Prämisse) und einer rechten Seite (Konklusion), die jeweils ein Wort bestehend aus Terminalen und Nichtterminalen sind. Die linke Seite muss mindestens ein Nichtterminal beinhalten und die rechte Seite kann dabei im Gegensatz zur linken Seite auch das leere Wort (im Folgenden mit $\varepsilon$ symbolisiert) sein, also das Wort der Länge Null: $P \subseteq \left( N \cup \Sigma \right)^* \times \left( N \cup \Sigma \right)^*$

Eine Grammatik ist in Normalform genau dann wenn gilt:

$P \subseteq N^* \times \left( N \cup \Sigma \right)^*$

Eine Regel kann auf ein Wort, bestehend aus Terminalen und Nichtterminalen, angewendet werden, wobei ein beliebiges Vorkommen der linken Seite der Regel im Wort durch die rechte Seite der Regel ersetzt wird. Für solche Produktionen hat sich folgende Schreibweise eingebürgert:

$w \rightarrow w'$

Für $w$ , $w'$ gilt dann die so genannte Transitionsrelation, eine Folge von Anwendungen solcher Regeln bezeichnet man als Ableitung.

Von G erzeugte Sprache

Eine Grammatik $G$ erzeugt eine formale Sprache $L \left( G \right)$ , die aus allen Wörtern besteht, die nur aus Terminalen bestehen und vom Startsymbol mit einer endlichen Anzahl von Schritten abgeleitet werden können:

$L \left( G \right) := \left\{ w \in \Sigma^* | S \Rightarrow_G^* w \right\}$

$\Rightarrow_G$ symbolisiert hierbei die so genannte Transitionsrelation, siehe dort. Der Stern in $\Rightarrow^*$ bedeutet nach einer beliebigen Anzahl von Schritten, also die reflexiv-transitive Hülle der Relation $\Rightarrow$ .

Beispiel

Wir betrachten die Grammatik mit den Terminalen $\{a, b\}$ , den Nichtterminalen $\{S, A, B\}$ mit dem Startsymbol $S$ und den Regeln $\begin{matrix}S&\to&ABS\\
S&\to&\varepsilon\\
BA&\to&AB\\
BS&\to&b\\
Bb&\to&bb\\
Ab&\to&ab\\
Aa&\to&aa\end{matrix}$

Sie definiert die Sprache aller Wörter der Form $a^n b^n$ mit $n \in \mathbb N$ , d. h. $n$ Kopien von $a$ gefolgt von $n$ Kopien von $b$ .

Hierbei ist zu beachten, dass dies nicht die einzige Grammatik ist, die diese Sprache erzeugt. Eine weitere Grammatik zur Erzeugung von $\{a^n b^n | n \in \mathbb N\}$ ist die mit diesen Regeln

$\begin{matrix}S&\to& ASB\ |\ \varepsilon\\
A&\to&a\\
B&\to&b\end{matrix}$

oder auch nur schlicht:

$\begin{matrix}S&\to&aSb\ |\ \varepsilon\end{matrix}$

Man sieht also, dass es zur Erzeugung einer Sprache mehrere (genaugenommen: abzählbar unendlich viele) Grammatiken gibt.

Man klassifiziert verschiedene Typen von Grammatiken in der so genannten Chomsky-Hierarchie. Die obige wäre z. B. vom Typ 2.

Siehe auch

Formale Sprachen | Theoretische Informatik | Compilerbau | Linguistik

Gourt Home::Gourt :: Formale Grammatik

Grundlagen

Definition

Von G erzeugte Sprache

Beispiel

Siehe auch