Theoretische Informatik

KAPITEL 6 Reguläre Sprachen

Das Konzept regulärer Sprachen (Sprachen vom Typ 3) wird in vielen Bereichen angewandt. Zu den wichtigsten zählen der Schaltkreisentwurf und die lexikalische Analyse beim Kompilieren von Programmen höherer Programmiersprachen. Reguläre Sprachen wurden in Abschnitt 5, Seite 195 mithilfe regulärer Grammatiken definiert. In diesem Kapitel stellen wir äquivalente Formalismen für reguläre Sprachen vor: endliche Automaten, reguläre Ausdrücke und Syntaxdiagramme.

6.1 Endliche Automaten

Während für die Hardwarespezifikation endliche Automaten als sequentielle Ein-/Ausgabemaschinen eingesetzt werden (Mealy and Moore-Automaten), werden sie beim Compilerbau als Sprachakzeptoren verwendet.

Wir beschäftigen uns hier nur mit endlichen Automaten als Sprachakzeptoren. Endliche Automaten können als eine sehr eingeschränkte Variante von Turingmaschinen angesehen werden, die mit einem Eingabeband ausgerüstet sind, auf dem der Lesekopf nur nach rechts bewegt werden kann und denen kein weiteres Band zur Verfügung steht (siehe Abbildung 6.1.2).

Ein endlicher Automat besteht also im Wesentlichen nur aus der endlichen Kontrolle (den Zuständen und der übergangsfunktion) und dem Eingabeband. Das einzige zur Verfügung stehende Speichermedium sind die Zustände.

6.1.1 Deterministische endliche Automaten

Wir betrachten zunächst deterministische endliche Automaten, für die wir die Abkürzung DEA verwenden. In Abschnitt 6.1.2 werden wir die nichtdeterministische Variante untersuchen. Initial steht das Eingabewort auf dem Eingabeband. In jedem Schritt (Konfigurationswechsel) wird der Lesekopf auf dem Eingabeband um eine Position nach rechts verschoben. Sobald das letzte Zeichen der Eingabe gelesen ist, hält die Berechnung an. Eine Berechnung ist entweder akzeptierend (wenn der Automat einen Endzustand erreicht hat) oder verwerfend. Jede Berechnung, in welcher der Automat anhält, ohne das Eingabewort zu Ende gelesen zu haben, ist verwerfend. Man beachte den Unterschied des Akzeptanz- und Terminierungsverhaltens eines DEAs zu dem einer Turingmaschine. Hört die Berechnung verfrüht auf (noch bevor das Eingabewort vollständig gelesen wurde), dann akzeptiert der DEA nicht, unabhängig vom erreichten Zustand. Während eine Turingmaschine stets anhält, sobald ein Endzustand erreicht ist, geht die Berechnung eines DEAs in einem Endzustand weiter, sofern die Eingabe noch nicht vollständig gelesen ist.