Vom Kellerautomaten zur Grammatik
Umwandlung eines Kellerautomaten in eine Grammatik
Wir betrachten den folgenden Kellerautomaten zur Erkennung der Sprache Lab = {anbn | n = 1, 2, 3, ...} der Klammerausdrücke:
Mit den Menupunkten [Convert][Convert to Grammar] erhält man zunächst eine Fehlermeldung:
Transitions must pop 1 and push 0 or 2
.
Wir ändern den Kellerautomaten geringfügig ab:
Mit den Menupunkten [Convert][Convert to Grammar] erhält man jetzt eine komplizierte Grammatik.
Mit [Export] wird sie zu folgender Grammatik vereinfacht:
Aufgabe 1
Probiere das selbst einmal aus. Versuche auch, zu einem weiteren Kellerautomaten eine Grammatik mit JFlap zu erzeugen. Beachte dabei, dass JFlap nur Kellerautomaten umwandelt, die bestimmte Einschränkungen erfüllen (z.B. dürfen keine Sonderzeichen als Eingabesymbole benutzt werden).