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