Formale Grammatik: Unterschied zwischen den Versionen

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…“
 
Keine Bearbeitungszusammenfassung
 
Zeile 2: Zeile 2:


==Definition==
==Definition==
Eine '''formale Grammatik''' ist ein 4-Tupel <math>G = (N, T, P, S)</math>:
Eine '''formale Grammatik''' ist ein 4-Tupel <math>G = (N; T; P; S)</math>. Ein Tupel ist eine geordnete Zusammenstellung: Jeder der vier Bestandteile hat seinen festen Platz. Die Bestandteile stehen in runden Klammern und werden durch Semikolons getrennt:


* <math>N</math> ist die endliche [[Menge]] der '''Nichtterminale'''. Sie sind Platzhalter für Strukturen, die noch durch Regeln ersetzt werden.
* <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 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>N \cap T = \emptyset</math>.
* <math>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. Kein Zeichen ist zugleich Nichtterminal und Terminal: <math>N \cap T = \emptyset</math>.
* <math>P</math> ist eine endliche Menge von '''Regeln''' (Produktionen) der Form <math>\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>P</math> ist eine endliche Menge von '''Regeln''' (Produktionen) der Form <math>\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>S \in N</math> ist das '''Startsymbol'''.
* <math>S \in N</math> ist das '''Startsymbol'''.


Die Reihenfolge der Bestandteile im Tupel ist nicht entscheidend, manche Quellen schreiben <math>(N, T, S, P)</math>.
Die Reihenfolge der Bestandteile im Tupel ist eine Vereinbarung, manche Quellen schreiben <math>(N; T; S; P)</math>.
 
Meist gelten diese Schreibweisen: Nichtterminale sind Großbuchstaben, Terminale sind Kleinbuchstaben, Ziffern oder Sonderzeichen. Ist nichts anderes angegeben, ist <math>S</math> das Startsymbol. Verbindlich ist diese Übereinkunft nicht: In den Beispielen dieses Wikis zum Kaffeeautomaten sind die Großbuchstaben <math>K</math> und <math>E</math> Terminale. Steht in jeder Regel links genau ein Zeichen, lassen sich die Nichtterminale an den linken Seiten der Regeln ablesen, alle übrigen Zeichen sind Terminale. Stehen links mehrere Zeichen, müssen <math>N</math> und <math>T</math> angegeben sein.


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


==Ableitung==
==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>\Rightarrow</math> geschrieben. Zu einer Regel <math>\alpha \to \beta</math> gehört also der Schritt <math>u\alpha v \Rightarrow u\beta v</math> für alle Zeichenfolgen <math>u, v \in (N \cup T)^*</math>.
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>\Rightarrow</math> geschrieben. Zu einer Regel <math>\alpha \to \beta</math> gehört also der Schritt <math>u\alpha v \Rightarrow u\beta v</math>. Dabei sind <math>u</math> und <math>v</math> beliebige Zeichenfolgen aus Nichtterminalen und Terminalen, die unverändert stehen bleiben. Die Menge all dieser Zeichenfolgen wird <math>(N \cup T)^*</math> geschrieben, auch die leere Zeichenfolge gehört dazu.


<math>\Rightarrow^*</math> steht für null oder mehr Ableitungsschritte. Die Ableitung beginnt beim Startsymbol und ist fertig, wenn nur noch Terminale übrig sind.
<math>\Rightarrow^*</math> steht für null oder mehr Ableitungsschritte. Die Ableitung beginnt beim Startsymbol und ist fertig, wenn nur noch Terminale übrig sind. Ein Wort ist '''ableitbar''', wenn es eine solche Ableitung gibt.


==Erzeugte Sprache==
==Erzeugte Sprache==
Zeile 23: Zeile 25:
:<math>L(G) = \{w \in T^* \mid S \Rightarrow^* w\}</math>
:<math>L(G) = \{w \in T^* \mid S \Rightarrow^* w\}</math>


<math>T^*</math> ist die Menge aller Wörter über <math>T</math> einschließlich des leeren Wortes <math>\varepsilon</math>. Zeichenfolgen mit Nichtterminalen gehören nicht zu <math>L(G)</math>. Zwei Grammatiken sind gleichwertig, wenn sie dieselbe Sprache erzeugen.
Gelesen wird die Formel so: <math>L(G)</math> ist die Menge aller Wörter <math>w</math> über <math>T</math>, für die gilt, dass <math>w</math> aus <math>S</math> ableitbar ist (zur Schreibweise siehe [[Formale Sprache#Beschreibung formaler Sprachen|Mengenschreibweise]]). <math>T^*</math> ist die Menge aller Wörter über <math>T</math> einschließlich des leeren Wortes <math>\varepsilon</math>. Zeichenfolgen mit Nichtterminalen gehören nicht zu <math>L(G)</math>. Zwei Grammatiken sind gleichwertig, wenn sie dieselbe Sprache erzeugen.
 
Um zu zeigen, dass ein Wort zu <math>L(G)</math> gehört, genügt eine Ableitung. Um zu zeigen, dass ein Wort nicht dazugehört, braucht es eine Eigenschaft, die alle ableitbaren Wörter haben und die dem Wort fehlt.


==Beispiele==
==Beispiele==
===Satzbau beschreiben===
===Satzbau beschreiben===
Der Artikel [[Syntax]] beschreibt den Satzbau englischer Sätze mit Regeln. Als Grammatik gelesen sind <math>\text{Satz}</math>, <math>\text{Subjekt}</math>, <math>\text{Prädikat}</math> und <math>\text{Objekt}</math> die Nichtterminale, <math>\text{Satz}</math> ist das Startsymbol. Die Terminale sind die englischen Wörter. Die Regeln lauten:
Der Artikel [[Syntax]] beschreibt den Satzbau englischer Sätze mit Regeln. Als Grammatik gelesen sind <math>\text{Satz}</math>, <math>\text{Subjekt}</math>, <math>\text{Prädikat}</math> und <math>\text{Objekt}</math> die Nichtterminale, <math>\text{Satz}</math> ist das Startsymbol. Die Terminale sind die englischen Wörter und Wortgruppen wie „soccer players“. Die Regeln lauten:


:<math>\text{Satz} \to \text{Subjekt Prädikat Objekt}</math>
:<math>\text{Satz} \to \text{Subjekt Prädikat Objekt}</math>
Zeile 53: Zeile 57:


Nach Schritt 4 stehen nur noch Terminale da. Die Ableitung ist fertig.
Nach Schritt 4 stehen nur noch Terminale da. Die Ableitung ist fertig.
===Grammatik als 4-Tupel angeben===
Gegeben sind die Regeln einer Grammatik:
:<math>S \to 0S1 \mid 01</math>
Gesucht ist die Grammatik als 4-Tupel <math>G = (N; T; P; S)</math>.
# '''Nichtterminale:''' Links vom Pfeil steht nur <math>S</math>, also gilt <math>N = \{S\}</math>.
# '''Terminale:''' Alle übrigen Zeichen der Regeln sind Terminale, also gilt <math>T = \{0; 1\}</math>.
# '''Regeln:''' Der Strich trennt zwei Alternativen. Die Regelmenge enthält deshalb zwei Regeln: <math>P = \{S \to 0S1; S \to 01\}</math>.
# '''Startsymbol:''' Es ist nichts anderes angegeben, also ist <math>S</math> das Startsymbol.
Damit lautet die Grammatik <math>G = (\{S\}; \{0; 1\}; P; S)</math>.


===Wort ableiten===
===Wort ableiten===
Die Grammatik hat das Startsymbol <math>S</math>, die Terminale <math>0</math> und <math>1</math> und diese Regeln:
Die Grammatik aus dem vorigen Beispiel hat das Startsymbol <math>S</math>, die Terminale <math>0</math> und <math>1</math> und diese Regeln:


:<math>S \to 0S1 \mid 01</math>
:<math>S \to 0S1 \mid 01</math>


Das Wort <code>000111</code> wird so abgeleitet:
Das Wort <math>000111</math> wird so abgeleitet:


:<math>S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 000111</math>
:<math>S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 000111</math>
Zeile 72: Zeile 90:
Gesucht ist <math>L(G)</math> für die Grammatik aus dem Beispiel [[#Wort ableiten|Wort ableiten]] mit den Regeln <math>S \to 0S1</math> und <math>S \to 01</math>.
Gesucht ist <math>L(G)</math> für die Grammatik aus dem Beispiel [[#Wort ableiten|Wort ableiten]] mit den Regeln <math>S \to 0S1</math> und <math>S \to 01</math>.


Jede Ableitung beginnt mit <math>S</math>. Jeder Schritt mit <math>S \to 0S1</math> setzt links vom <math>S</math> eine <math>0</math> und rechts eine <math>1</math>. Nach <math>n - 1</math> solchen Schritten steht <math>0^{n-1} S 1^{n-1}</math> da. Die Regel <math>S \to 01</math> ersetzt dann <math>S</math> durch <math>01</math> und beendet die Ableitung. Nur diese Regel entfernt das <math>S</math>. Das Ergebnis ist <math>0^n 1^n</math>.
Jede Ableitung beginnt mit <math>S</math>. Jeder Schritt mit <math>S \to 0S1</math> setzt links vom <math>S</math> eine <math>0</math> und rechts eine <math>1</math>. Nach <math>n - 1</math> solchen Schritten steht <math>0^{n-1} S 1^{n-1}</math> da. Die Schreibweise mit Exponent ist eine [[Wort#Wortpotenz|Wortpotenz]]: Der Exponent gibt an, wie oft das Zeichen hintereinander steht. Die Regel <math>S \to 01</math> ersetzt dann <math>S</math> durch <math>01</math> und beendet die Ableitung. Nur diese Regel entfernt das <math>S</math>. Das Ergebnis ist <math>0^n 1^n</math>.


Die kürzesten Wörter sind <code>01</code>, <code>0011</code> und <code>000111</code>. Es gilt:
Die kürzesten Wörter sind <math>01</math>, <math>0011</math> und <math>000111</math>. Es gilt:


:<math>L(G) = \{0^n 1^n \mid n \geq 1\}</math>
:<math>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>S \to 01</math> endet.
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>S \to 01</math> endet.
===Nicht ableitbares Wort begründen===
Für die Grammatik mit den Regeln <math>S \to 0S1</math> und <math>S \to 01</math> soll geprüft werden, ob <math>001</math> und <math>0101</math> zu <math>L(G)</math> gehören.
* '''<math>001</math>:''' Jede der beiden Regeln erzeugt genau eine <math>0</math> und genau eine <math>1</math>. Jedes ableitbare Wort enthält deshalb gleich viele Nullen und Einsen. Das Wort <math>001</math> enthält zwei Nullen, aber nur eine Eins. Es ist nicht ableitbar: <math>001 \notin L(G)</math>.
* '''<math>0101</math>:''' Das Wort enthält zwar gleich viele Nullen und Einsen. Die Regel <math>S \to 0S1</math> setzt aber die <math>0</math> vor das <math>S</math> und die <math>1</math> dahinter, und die Regel <math>S \to 01</math> ersetzt das <math>S</math> durch <math>01</math>. In jedem ableitbaren Wort stehen deshalb alle Nullen vor allen Einsen. In <math>0101</math> folgt auf eine <math>1</math> noch eine <math>0</math>. Es ist nicht ableitbar: <math>0101 \notin L(G)</math>.
Ausprobieren einzelner Ableitungen reicht für eine solche Begründung nicht aus, denn es müssten alle Ableitungen betrachtet werden. Die Begründung nennt deshalb eine Eigenschaft aller ableitbaren Wörter, die dem geprüften Wort fehlt.
===Grammatik gegen eine Beschreibung prüfen===
Eine Grammatik soll genau die Wörter erzeugen, die aus mindestens einer <math>0</math> und einer abschließenden <math>1</math> bestehen: <math>01</math>, <math>001</math>, <math>0001</math> und so weiter. Vorgeschlagen wird:
:<math>S \to 0S \mid 1</math>
'''Schritt 1: Gewünschte Wörter ableiten.''' Das Wort <math>001</math> ist ableitbar:
:<math>S \Rightarrow 0S \Rightarrow 00S \Rightarrow 001</math>
'''Schritt 2: Nach unpassenden Wörtern suchen.''' Geprüft werden die kürzesten Ableitungen und Ableitungen, die eine Regel mehrfach anwenden. Hier genügt schon die kürzeste: Sie wendet sofort die Regel <math>S \to 1</math> an und erzeugt das Wort <math>1</math>. Dieses Wort enthält keine <math>0</math> und passt nicht zur Beschreibung. Die Grammatik erzeugt also ein Wort zu viel. Nicht jeder Fehler zeigt sich so früh: Manche unpassenden Wörter entstehen erst, wenn eine Regel, die sich wiederholen lässt, mehrfach angewendet wird.
'''Schritt 3: Grammatik korrigieren.''' Die erste <math>0</math> muss erzwungen werden. Das Startsymbol erzeugt deshalb zuerst eine <math>0</math> und übergibt dann an ein zweites Nichtterminal <math>A</math>. <math>A</math> hängt weitere Nullen an oder schließt mit <math>1</math> ab:
:<math>S \to 0A</math>
:<math>A \to 0A \mid 1</math>
'''Schritt 4: Erneut prüfen.''' Jede Ableitung beginnt jetzt mit <math>S \Rightarrow 0A</math>, jedes ableitbare Wort beginnt also mit einer <math>0</math>. Das Wort <math>1</math> ist nicht mehr ableitbar, <math>001</math> weiterhin:
:<math>S \Rightarrow 0A \Rightarrow 00A \Rightarrow 001</math>
Eine Grammatik passt nur dann zu einer Beschreibung, wenn beides gilt: Jedes beschriebene Wort ist ableitbar, und jedes ableitbare Wort passt zur Beschreibung.


[[Kategorie:Formale Sprachen]]
[[Kategorie:Formale Sprachen]]
[[Kategorie:AHR I Informatik LK]]
[[Kategorie:AHR I Informatik LK]]