Vom Kellerautomaten zur Grammatik

Umwandlung eines Kellerautomaten in eine Grammatik

Wir betrachten den folgenden Kellerautomaten zur Erkennung der Sprache L_ab = {aⁿbⁿ | 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).