Strategien zur Erzeugung von Kellerautomaten

Erzeugung von Kellerautomaten mit unterschiedlichen Strategien

Wir betrachten eine Grammatik für die Sprache L_RA der vereinfachten Rechenausdrü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. z+z*(z+z)) erzeugen.

Mit den Menupunkten [Convert][Convert CFG to PDA (LR)] lässt sich ein weiterer Kellerautomaten aus der vorgegebenen Grammatik erzeugen:

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. z+z*(z+z)) erzeugen.

Aufgabe 1

(a) Probiere das selbst einmal aus.

(b) Worin unterscheiden sich die erzeugten Kellerautomaten? Vergleiche die Zustandsübergänge und die diesen Übergängen zu Grunde liegenden Verarbeitungsstrategien.