Linksableitung an einem Beispiel

Dieses interaktive Element veranschaulicht das schrittweise Erzeugen eines Wortes aus den Produktionsregeln P einer Grammatik G = (N, Σ, P, S).

Aus den gegebenen Produktionsregeln der Grammatik G soll das Wort w = ddabbaa abgeleitet werden.

Bei der folgenden Wortgenerierung kommt die sogenannte Linksableitung zum Einsatz, bei der Nichtterminalsymbole während der Termersetzung von links nach rechts ersetzt werden. Außerdem ist für jeden Ableitungsschritt eindeutig, welche der Produktionsregeln angewendet werden muss.

Linksableitung des Wortes w = ddabbaa:

Hinweise zum Spiel:

Das Dreieckssymbol zeigt an, welches Nichtterminalsymbol (A, B, S) im Term aktuell zu ersetzen ist.
Die Eingabe des Symbols ε (dem Leeren Wort) kann durch den ε-Button erzielt werden.
Der Button "Lösung" gibt dir die Lösung des aktuellen Substitutionsschrittes an.

S dS

A aA

B bBA

S A

A aB

B ε

A a

Zur Übersichtsseite