Formale Grammatik

Version vom 8. November 2026, 09:05 Uhr von Flbkwikiadmin (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „Eine Grammatik beschreibt eine Sprache durch Regeln, mit denen sich ihre Wörter erzeugen lassen. So ist auch die Syntax von Programmiersprachen festgelegt. ==Definition== Eine '''formale Grammatik''' ist ein 4-Tupel <math>G = (N, T, P, S)</math>: * <math>N</math> ist die endliche Menge der '''Nichtterminale'''. Sie sind Platzhalter für Strukturen, die noch durch Regeln ersetzt werden. * <math>T</math> ist die endli…“)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

Eine Grammatik beschreibt eine Sprache durch Regeln, mit denen sich ihre Wörter erzeugen lassen. So ist auch die Syntax von Programmiersprachen festgelegt.

Definition

Eine formale Grammatik ist ein 4-Tupel [math]\displaystyle{ G = (N, T, P, S) }[/math]:

  • [math]\displaystyle{ N }[/math] ist die endliche Menge der Nichtterminale. Sie sind Platzhalter für Strukturen, die noch durch Regeln ersetzt werden.
  • [math]\displaystyle{ T }[/math] ist die endliche Menge der Terminale. Das sind die Zeichen, aus denen die Wörter der Sprache bestehen, also das Alphabet der erzeugten Sprache. Es gilt [math]\displaystyle{ N \cap T = \emptyset }[/math].
  • [math]\displaystyle{ P }[/math] ist eine endliche Menge von Regeln (Produktionen) der Form [math]\displaystyle{ \alpha \to \beta }[/math]. Links steht eine Folge aus Nichtterminalen und Terminalen, die mindestens ein Nichtterminal enthält. Rechts steht eine beliebige, auch leere Folge aus Nichtterminalen und Terminalen.
  • [math]\displaystyle{ S \in N }[/math] ist das Startsymbol.

Die Reihenfolge der Bestandteile im Tupel ist nicht entscheidend, manche Quellen schreiben [math]\displaystyle{ (N, T, S, P) }[/math].

Regeln mit derselben linken Seite lassen sich mit dem Strich [math]\displaystyle{ \mid }[/math] zusammenfassen: [math]\displaystyle{ \alpha \to \beta_1 \mid \beta_2 }[/math] steht für die beiden Regeln [math]\displaystyle{ \alpha \to \beta_1 }[/math] und [math]\displaystyle{ \alpha \to \beta_2 }[/math]. Die Form der Regeln bestimmt den Typ einer Grammatik, siehe Chomsky-Hierarchie.

Ableitung

Eine Ableitung erzeugt ein Wort aus dem Startsymbol. Ein Ableitungsschritt ersetzt in einer Zeichenfolge die linke Seite einer Regel durch ihre rechte Seite und wird [math]\displaystyle{ \Rightarrow }[/math] geschrieben. Zu einer Regel [math]\displaystyle{ \alpha \to \beta }[/math] gehört also der Schritt [math]\displaystyle{ u\alpha v \Rightarrow u\beta v }[/math] für alle Zeichenfolgen [math]\displaystyle{ u, v \in (N \cup T)^* }[/math].

[math]\displaystyle{ \Rightarrow^* }[/math] steht für null oder mehr Ableitungsschritte. Die Ableitung beginnt beim Startsymbol und ist fertig, wenn nur noch Terminale übrig sind.

Erzeugte Sprache

Die von [math]\displaystyle{ G }[/math] erzeugte Sprache enthält alle Wörter aus Terminalen, die sich aus dem Startsymbol ableiten lassen:

[math]\displaystyle{ L(G) = \{w \in T^* \mid S \Rightarrow^* w\} }[/math]

[math]\displaystyle{ T^* }[/math] ist die Menge aller Wörter über [math]\displaystyle{ T }[/math] einschließlich des leeren Wortes [math]\displaystyle{ \varepsilon }[/math]. Zeichenfolgen mit Nichtterminalen gehören nicht zu [math]\displaystyle{ L(G) }[/math]. Zwei Grammatiken sind gleichwertig, wenn sie dieselbe Sprache erzeugen.

Beispiele

Satzbau beschreiben

Der Artikel Syntax beschreibt den Satzbau englischer Sätze mit Regeln. Als Grammatik gelesen sind [math]\displaystyle{ \text{Satz} }[/math], [math]\displaystyle{ \text{Subjekt} }[/math], [math]\displaystyle{ \text{Prädikat} }[/math] und [math]\displaystyle{ \text{Objekt} }[/math] die Nichtterminale, [math]\displaystyle{ \text{Satz} }[/math] ist das Startsymbol. Die Terminale sind die englischen Wörter. Die Regeln lauten:

[math]\displaystyle{ \text{Satz} \to \text{Subjekt Prädikat Objekt} }[/math]
[math]\displaystyle{ \text{Subjekt} \to \text{She} \mid \text{He} }[/math]
[math]\displaystyle{ \text{Prädikat} \to \text{loves} \mid \text{kicked} \mid \text{likes} }[/math]
[math]\displaystyle{ \text{Objekt} \to \text{soccer players} \mid \text{swimming} \mid \text{the ball} }[/math]

Das Subjekt hat 2 Möglichkeiten, das Prädikat 3 und das Objekt 3. Die Sprache enthält deshalb [math]\displaystyle{ 2 \cdot 3 \cdot 3 = 18 }[/math] Sätze. Die Grammatik prüft nur die Form, nicht die Bedeutung: Jede Kombination ist ein gültiger Satz.

Der Satz „She likes soccer players“ entsteht in vier Schritten:

Schritt Zeichenfolge angewendete Regel
0 [math]\displaystyle{ \text{Satz} }[/math] Startsymbol
1 [math]\displaystyle{ \text{Subjekt Prädikat Objekt} }[/math] [math]\displaystyle{ \text{Satz} \to \text{Subjekt Prädikat Objekt} }[/math]
2 [math]\displaystyle{ \text{She Prädikat Objekt} }[/math] [math]\displaystyle{ \text{Subjekt} \to \text{She} }[/math]
3 [math]\displaystyle{ \text{She likes Objekt} }[/math] [math]\displaystyle{ \text{Prädikat} \to \text{likes} }[/math]
4 [math]\displaystyle{ \text{She likes soccer players} }[/math] [math]\displaystyle{ \text{Objekt} \to \text{soccer players} }[/math]

Nach Schritt 4 stehen nur noch Terminale da. Die Ableitung ist fertig.

Wort ableiten

Die Grammatik hat das Startsymbol [math]\displaystyle{ S }[/math], die Terminale [math]\displaystyle{ 0 }[/math] und [math]\displaystyle{ 1 }[/math] und diese Regeln:

[math]\displaystyle{ S \to 0S1 \mid 01 }[/math]

Das Wort 000111 wird so abgeleitet:

[math]\displaystyle{ S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 000111 }[/math]
  • Schritt 1: Die Regel [math]\displaystyle{ S \to 0S1 }[/math] ersetzt [math]\displaystyle{ S }[/math] durch [math]\displaystyle{ 0S1 }[/math].
  • Schritt 2: Dieselbe Regel ersetzt das [math]\displaystyle{ S }[/math] in der Mitte erneut. Es entsteht [math]\displaystyle{ 00S11 }[/math].
  • Schritt 3: Die Regel [math]\displaystyle{ S \to 01 }[/math] ersetzt das [math]\displaystyle{ S }[/math] durch [math]\displaystyle{ 01 }[/math]. Es bleiben nur Terminale übrig.

Damit gilt [math]\displaystyle{ S \Rightarrow^* 000111 }[/math] und [math]\displaystyle{ 000111 \in L(G) }[/math].

Erzeugte Sprache bestimmen

Gesucht ist [math]\displaystyle{ L(G) }[/math] für die Grammatik aus dem Beispiel Wort ableiten mit den Regeln [math]\displaystyle{ S \to 0S1 }[/math] und [math]\displaystyle{ S \to 01 }[/math].

Jede Ableitung beginnt mit [math]\displaystyle{ S }[/math]. Jeder Schritt mit [math]\displaystyle{ S \to 0S1 }[/math] setzt links vom [math]\displaystyle{ S }[/math] eine [math]\displaystyle{ 0 }[/math] und rechts eine [math]\displaystyle{ 1 }[/math]. Nach [math]\displaystyle{ n - 1 }[/math] solchen Schritten steht [math]\displaystyle{ 0^{n-1} S 1^{n-1} }[/math] da. Die Regel [math]\displaystyle{ S \to 01 }[/math] ersetzt dann [math]\displaystyle{ S }[/math] durch [math]\displaystyle{ 01 }[/math] und beendet die Ableitung. Nur diese Regel entfernt das [math]\displaystyle{ S }[/math]. Das Ergebnis ist [math]\displaystyle{ 0^n 1^n }[/math].

Die kürzesten Wörter sind 01, 0011 und 000111. Es gilt:

[math]\displaystyle{ L(G) = \{0^n 1^n \mid n \geq 1\} }[/math]

Die Sprache enthält alle Wörter, die aus gleich vielen Nullen und Einsen bestehen und in denen alle Nullen vor den Einsen stehen. Das leere Wort gehört nicht dazu, weil jede Ableitung mit [math]\displaystyle{ S \to 01 }[/math] endet.