Vom Automaten zur Grammatik

Umwandlung eines Automaten für Binärzahlen

Einen endlichen Automaten zur Erkennung der Sprache L_Bin = {0, 1, 10, 11, 100, 101, 110, 111, 1000, ...} der Binärzahlen lässt sich leicht erstellen:

Wenn man in JFlap die Menupunkte [Convert][Convert to Grammar] auswählt, dann lässt sich zum gegebenen erkennenden Automaten schrittweise eine Grammatik erzeugen. Man muss hierzu nur die Eingaben an den Zustandsübergängen und die Endzustände anklicken.

Aufgabe 1

Probiere das selbst einmal aus. Welche Grammatik erhält man zum gegebenen Akzeptor?

Aufgabe 2

Wie wird die Grammatik aus dem Akzeptor erzeugt? Wenn du es verstanden hast, dann gib einen Automaten vor, erzeuge selbst die zugehörige Grammatik und überprüfe deinen Vorschlag.