Grammatiken und Ableitungen

Ein Automat prüft Wörter. Eine Grammatik geht den umgekehrten Weg: Sie erzeugt die Wörter einer Sprache mit Ersetzungsregeln.

• Nichtterminale N:Hilfssymbole, die noch ersetzt werden — meist Großbuchstaben wie S, A.
• Terminale T:Zeichen der fertigen Wörter — meist Kleinbuchstaben oder Ziffern.
• Startsymbol:ein Nichtterminal, meist S — damit beginnt jede Ableitung.
• Produktionsregel:linke Seite → rechte Seite: „ersetze links durch rechts“.
• Oder-Strich:A → 0A | 1A | ε fasst drei Regeln zusammen.
• ε-Regel:A → ε lässt A ersatzlos verschwinden.

So wird eine Grammatik nach den Ergänzenden Hinweisen notiert — hier für Binärzahlen ohne führende Null:

N =

{S, A}

T =

{0, 1}

Startsymbol:

S

Produktionsregeln:

S → 1A | 0
A → 0A | 1A | ε

Herleitung:

• Ableitungsschritt:\(u\Rightarrow v\): ein Nichtterminal in u wird durch die rechte Seite einer seiner Regeln ersetzt.
• Satzform:jedes Zwischenergebnis — Terminale und Nichtterminale gemischt.
• Ableitung:\(S\Rightarrow\ldots\Rightarrow w\), bis nur Terminale übrig sind; kurz \(S\Rightarrow^* w\).
• Erzeugte Sprache:\(L(G)=\{w\in T^*\mid S\Rightarrow^* w\}\).
• Linksableitung:immer das am weitesten links stehende Nichtterminal ersetzen (Rechtsableitung: das rechte).
• Ableitungsbaum:Wurzel S, innere Knoten Nichtterminale, Kinder = rechte Seite der Regel; die Blätter von links nach rechts ergeben das Wort.

Leite Schritt für Schritt ab (▶ oder „Nächster Schritt“) und beobachte, wie der Baum wächst. Schalte zwischen Links- und Rechtsableitung um und vergleiche die Reihenfolge. Wickle zum Schluss den fertigen Baum ab.

Halte fest: Links- und Rechtsableitung wenden die Regeln in anderer Reihenfolge an — der fertige Baum ist derselbe. Liest man seine Blätter von links nach rechts, entsteht das Wort; ε-Blätter fallen dabei weg.