Vom DEA zur Grammatik
Worum geht es hier?
Eine Grammatik beschreibt, wie die Wörter einer Sprache gebildet werden. Ein Automat erkennt, ob ein Wort zu einer Sprache gehört. In diesem Abschnitt untersuchst du den Zusammenhang zwischen diesen beiden Beschreibungen: Wie lässt sich aus einem deterministischen endlichen Automaten eine Grammatik gewinnen, die genau die von ihm erkannte Sprache erzeugt?
Beispiel: Binärzahlen
Der folgende DEA erkennt die Sprache der Binärzahlen ohne führende Nullen.
Aufgabe 1 - Vom DEA zur Grammatik
Untersuche mit FLACI, wie sich der DEA in eine Grammatik umwandeln lässt.
- Erstelle den abgebildeten DEA in FLACI oder lade die Datei DEA_Binaerzahlen.json herunter und öffne sie in FLACI.
- Wähle im Menü Konvertieren den Eintrag Automat zu kfG aus, um eine Grammatik zum Automaten erzeugen zu lassen.
-
Teste die erzeugte Grammatik. Untersuche beispielsweise die Wörter
0,1,10und101sowie die Gegenbeispiele00und01. - Vollziehe nach, wie FLACI die Grammatik aus dem DEA erzeugt hat. Wie hängen die Zustände des Automaten mit den Nichtterminalen der Grammatik zusammen?
- Untersuche den Aufbau der Produktionen. Wo findest du die Übergänge und die Endzustände des Automaten in den Regeln wieder? Beschreibe die Struktur, die dir bei den rechten Seiten der Produktionen auffallen.