Beispiel für eine Ableitung
(s. Grammatik für Sprache2' aus 1.2.3)
 |
| |
Linksableitung:
Ersetzt wird das am weitesten links stehende Nichtterminal.
(vgl. Beispiel aus 2.1.2)
|
| |
Rechtsableitung:
Ersetzt wird das am weitesten rechts stehende Nichtterminal. (s.o.)
|
|
Gegeben ist eine Grammatik. Aber wie komme ich zur Sprache?
Die Phrasenstrukturregeln sind Ersetzungsregeln.
Die Symbole der linken Regelseite können durch die Symbole der rechten Regelseite ersetzt werden.
Ausgehend vom Startsymbol werden Regeln nun so angewendet, dass am Ende ein Wort komplett aus Terminalsymbolen bestehend entsteht.
Dieser Prozess wird Ableitung genannt.
| Terminalwort - Terminalalphabet - terminierte Ableitung |
Eine Ableitung (derivation) ist eine Relation zwischen Zeichenketten;
Ableitung in einem Schritt, direkte Ableitung: 
transitive und reflexive Hülle, Ableitung:
Man sagt, xm ist aus x1 ableitbar. |
 |
Ist eine Zeichenkette y in genau k Schritten aus x ableitbar, so schreibt man: 
Die Sprache, die von einer Grammatik erzeugt wird, ist dann: 
"Alle Zeichenketten bestehend aus Terminalsymbolen (je nach Terminologie Sätze/Wörter), die aus dem Startsymbol abgeleitet werden können."
"Liest" man eine Ableitung von rechts nach links, so spricht man von Reduktion.
Das Terminalwort wird auf das Startsymbol reduziert.
Dabei werden Teilwörter, die einer rechten Regelseite entsprechen, durch die Symbole der linken Regelseite ersetzt.
|
1
2
3
4
Von der Grammatik zur Sprache (2)