Endliche Automaten (2)

Die zulässigen Eingabefolgen, die vom Startzustand Z0 zum Endzustand Z5 führen, bilden offensichtlich eine Formale Sprache, die unser Automat erkennen kann. Wir wollen diesen Zusammenhang weiter untersuchen.

Wir lassen die Simulation der Ausgabetaste weg und zeichnen das Übergangsdiagramm etwas um:

Jeder zulässige Weg vom Startzustand Z0 zum Endzustand Z5 ist ein Wort einer Formalen Sprache; wir suchen dafür eine Grammatik. Tatsächlich können wir sie aus dem Diagramm oder auch aus der Übergangstafel direkt ablesen:
Z0 1 Z1
Z0 2 Z2
Z0 5 Z5
Z1 1 Z2
Z1 2 Z3
Z2 1 Z3
Z2 2 Z4
Z3 1 Z4
Z3 2 Z5
Z4 1 Z5
Z5
Dies sind Regeln einer regulären Grammatik für die Sprache der zulässigen Eingaben, bis auf die störende letzte Regel, die wir aber beseitigen können, indem wir Z5 auf den rechten Seiten einfach weglassen.

Umgekehrt können wir zu jeder regulären Grammatik systematisch einen endlichen Automaten für dieselbe Sprache konstruieren: Jedem Nichtterminalsymbol entspricht ein Zustand, das Startsymbol wird Anfangszustand. Die Regeln, auf deren rechter Seite nur ein Terminalsymbol steht, ergänzen wir um ein neues  Nichtterminalsymbol, das Endzustand wird. Die Übergänge ergeben sich direkt aus den Grammatikregeln.

zurück | Inhalt | Index | vor | Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36