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

Strategien zur Erzeugung von Kellerautomaten

Erzeugung von Kellerautomaten mit unterschiedlichen Strategien

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

JFlap - Ableitung

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

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

JFlap - Ableitung

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.

X

Fehler melden

X

Suche