Logo des digitalen Schulbuchs inf-schule.de. Schriftzug in Zustandsübergangsdiagramm eines endlichen Automaten.

Von der Grammatik zum Kellerautomaten

Umwandlung einer Grammatik in einen Kellerautomaten

Wir betrachten eine Grammatik für die Sprache Lab = {anbn | n = 1, 2, 3, ...} der Klammerausdrücke:

JFlap - Grammatik

Nach Eingabe der Grammatik bietet JFlap die Menupunkte [Convert][Convert CFG to PDA (LL)] an. Jetzt kann man einzelne Produktionen auswählen und sich die entsprechenden Zustandsübergänge im Kellerautomaten erzeugen lassen. Wenn alle Produktionen verarbeitet sind, erhält man folgenden Kellerautomaten:

JFlap - Kellerautomat

Mit [Export] kann man den erzeugten Kellerautomaten in ein neues Fenster kopieren. Mit [Input][Fast Run] lässt sich jetzt eine Ableitung zu einem Eingabewort (z.B. aabb) erzeugen.

JFlap - Ableitung

Aufgabe 1

(a) Probiere das selbst einmal aus. Analysiere den Zusammenhang zwischen der vorgegebenen Grammatik und dem erzeugten Kellerautomaten. Analysiere auch, was sich im Keller des Kellerautomaten abspielt, wenn ein Eingabewort verarbeitet wird.

(b) Der aus der Grammatik erzeugte Kellerautomat ist nichtdeterministisch. Woran erkennt man das?

X

Fehler melden

X

Suche