Von der Grammatik zum Kellerautomaten

Umwandlung einer Grammatik in einen Kellerautomaten

Wir betrachten eine Grammatik für die Sprache L_ab = {aⁿbⁿ | n = 1, 2, 3, ...} der Klammerausdrücke:

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:

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.

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?