Endliche Automaten (3)
Der aus einer regulären Grammatik schematisch
erhaltene Automat liefert uns ein Erzeugungsverfahren,
ist aber leider meistens nichtdeterministisch:
von einem Zustand aus kann es bei gleicher Eingabe mehrere
mögliche Übergänge geben.
Man kann ihn systematisch in einen äquivalenten
deterministischen Automaten umwandeln;
wie das geht, erfahren wir in der Automatentheorie.
So erhalten wir auch ein Entscheidungsverfahren;
der neue Automat kann allerdings recht groß werden.
Das Übergangsdiagramm unseres Automaten
betont die Zustände, deren Bezeichnung aber
für die erzeugte Sprache gar keine Rolle spielt.
Wenn wir die Zustände unterdrücken und stattdessen
die Übergänge hervorheben,
erhalten wir eine gleichwertige Darstellung,
aus der man die erzeugte Sprache noch besser ablesen kann:
Dies ist ein Sonderfall der Syntaxdiagramme, wobei im Diagramm
nur Terminalsymbole vorkommen; wie wir sehen konnten,
ist er gleichmächtig mit den endlichen Automaten,
und auch mit den regulären
Grammatiken (Klasse 3).
Jeder zulässige Weg vom Eingang zum Ausgang definiert ein Wort
der erzeugten Sprache.
Im allgemeinen Fall können in Syntaxdiagrammen außer den hier
rund gezeichneten Terminalsymbolen auch Nichtterminalsymbole vorkommen,
die man üblicherweise durch einen rechteckigen Kasten kennzeichnet;
für jedes davon ist ein beliebiges daraus ableitbares Wort
einzusetzen. Die genauen Regeln der Abarbeitung besprechen wir später.
Diese allgemeinen Syntaxdiagramme erfassen die
kontextfreien Sprachen (Klasse 2).
zurück |
Inhalt | Index |
vor |
Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36