Strategien zur Erzeugung von Kellerautomaten
Erzeugung von Kellerautomaten mit unterschiedlichen Strategien
Wir betrachten eine Grammatik für die Sprache LRA 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.