Grammatiken 13

Definition 13

Eine Grammatik ist ein $4$-Tupel $G=\left(V,\Sigma,P,S\right)$, das folgende Bedingungen erfüllt.

• $V$ ist eine endliche Menge, die Menge der Variablen
• $\Sigma$ ist eine endliche Menge, das Terminalalphabet
• $V\cap\Sigma=\emptyset$
• $S\in V$ Startsymbol
• $P$ ist die endliche Menge der Produktionen oder Regeln. Formal: $P\subset\left(V\cup\Sigma\right)^{+}\times\left(V\cup\Sigma\right)^{*}$ ist endlich.
• $\forall_{P}^{l\rightarrow r}:\left\vert l\right\vert _{V}\geq1$

Seien $u,v\in\left(V\cup\Sigma\right)^{*}$. Wir definieren die Relation $u\Rightarrow_{G}v$ ($u$ geht unter $G$ unmittelbar über in $v$), falls

• $\exists_{\left(V\cup\Sigma\right)^{*}}^{x,y}:u=xyz\wedge v=xy'z$
• $\left(y\rightarrow y'\right)\in P$

Wenn klar, ist welche Grammatik gemeint ist, so schreiben wir einfach $u\Rightarrow v$

Beispiel für Schreibweise (mit erweiterter Schreibweise / Backus-Naur-Form):

$$G := \left(V,\Sigma,P,S\right)$$

$$V := \left\{ S,N,Z\right\}$$

$$\Sigma := \left\{ 0,1,2,3,4,5,6,7,8,9,-,\epsilon\right\}$$

$$P := \{ S\rightarrow ZN;$$

$$Z\rightarrow\epsilon\vert-;$$

$$N\rightarrow1\vert 2\vert 3\vert 4\vert 5\vert 6\vert 7\vert 8\vert 9\vert NN\}$$

Ableitungen 14

Eine Folge von Wörtern $\left(w_{0},w_{1},\ldots,w_{n}\right)$ mit $w_{0}=S,w_{n}\in\Sigma^{*}$ und $w_{0}\Rightarrow w_{1}\Rightarrow\ldots\Rightarrow w_{n}$ heißt Ableitung von $w_{n}$.

Ein Wort $w\in\left(V\cup\Sigma\right)^{*}$, das also noch Variablen enthält (wie es typischerweise im Verlauf einer Ableitung vorkommt) heißt auch Satzform.

Ein Wort $w\in\left(\Sigma\right)^{*}$, das ausschließlich Terminale enthält heißt auch Terminalwort.

• Ableiten ist ein nichtdeterministischer Prozess (es steht im allgemeinen nicht fest, auf was etwas abgeleitet werden muss).

Sprache einer Grammatik 14

Die von $G=\left(V,\Sigma,P,S\right)$ dargestellte (erzeugte, definierte) Sprache ist:

$$L\left(G\right)=\left\{ w\in\Sigma^{*}\vert S\Rightarrow_{G}^{*}w\right\}$$

Dies bedeutet, das man mit einer beliebigen Kombination von Ableitungen, irgendwie zu dem Wort $w$ kommen können muss.

Darstellung von Ableitungen 16

Graphisch kann man sich das Ableiten wie ein endlich verzweigter, aber im allgemeinen unendlich großen Baum vorstellen. Mit $S$ als Wurzel, und Wörtern der Sprache als Blätter.