s n h m r u
i

Vom DEA zur Grammatik

Wird noch weiter angepasst.

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?

Der folgende DEA erkennt die Sprache der Binärzahlen ohne führende Nullen.

Aufgabe 1 - Vom DEA zur Grammatik

Untersuche, wie sich der DEA schrittweise in eine Grammatik umwandeln lässt:

  1. Wähle im Menü ... den Eintrag ... aus, um eine Grammatik zum Automaten erzeugen zu lassen.
  2. Teste die erzeugte Grammatik. Untersuche beispielsweise die Wörter 0, 1, 10 und 101 sowie die Gegenbeispiele 00 und 01.
  3. Vollziehe nach, wie die Grammatik aus dem DEA erzeugt wurde. Wie hängen die Zustände des Automaten mit den Nichtterminalen der Grammatik zusammen?
  4. 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.

Suche

v
100.130.2.3.2.1 Vom DEA zur Grammatik
Kopieren durch Anklicken

Rückmeldung geben