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

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:

JFlap - Kellerautomat

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:

JFlap - Kellerautomat

Mit den Menupunkten [Convert][Convert to Grammar] erhält man jetzt eine komplizierte Grammatik.

JFlap - Grammatik

Mit [Export] wird sie zu folgender Grammatik vereinfacht:

JFlap - Grammatik

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).

X

Fehler melden

X

Suche