Endliche Automaten und reguläre Sprachen

FLACI als Werkzeug

Zusammenhänge zwischen Sprachen und Automaten lassen sich sehr gut mit dem Werkzeug FLACI erkunden. Ziel dieses Abschnittes ist es, solche Zusammenhänge durch Experimente herauszufinden. In den weiteren Abschnitten werden die Zusammenhänge dann aufgegriffen und präzisiert.

Als Untersuchungsgegenstand wird in diesem Abschnitt die Sprache der Binärzahlen gewählt. Diese Sprache eignet sich für Untersuchungen, da sie recht einfach ist.

Die Sprache der Binärzahlen

Binärzahlen sind Zahlen, die im Dualsystem / Zweiersystem dargestellt sind und daher nur die Symbole 0 und 1 zur Zahldarstellung benutzen. Die folgende Zahlenreihe beschreibt, wie man im Dualsystem / Zweiersystem zählt:

Binärzahlen sind Wörter über dem Alphabet $\Sigma = {0, 1}$. Die Sprache der Binärzahlen $L_{Bin}$ besteht aus sämtlichen Wörtern über $\Sigma = {0, 1}$, die eine Binärzahl darstellen:

$L_{Bin} = {0, 1, 10, 11, 100, 101, 110, 111, 1000, ...}$

Umwandlung eines Automaten für Binärzahlen

Einen endlichen Automaten zur Erkennung der Sprache $L_{Bin} = {0, 1, 10, 11, 100, 101, 110, 111, 1000, ...}$ der Binärzahlen lässt sich leicht erstellen:

Wenn man in FLACI den Menupunkt "Konvertieren auswählt, dann lässt sich zum gegebenen erkennenden Automaten eine Grammatik erzeugen.

Aufgabe 1

Probiere das selbst einmal aus. Welche Grammatik erhält man zum gegebenen Akzeptor?

Aufgabe 2

Wie wird die Grammatik aus dem Akzeptor erzeugt? Wenn du es verstanden hast, dann gib einen Automaten vor, erzeuge selbst die zugehörige Grammatik und überprüfe deinen Vorschlag.

Von der Grammatik zum Automaten

Verarbeitung einer Grammatik für Binärzahlen

Die Sprache $L_{Bin} = {0, 1, 10, 11, 100, 101, 110, 111, 1000, ...}$ der Binärzahlen kann man mit einer Reihe von Grammatiken beschreiben, u.a. mit der folgenden:

A -> 1B
A -> 0C
A -> 1C
C -> EPSILON
B -> 0 B
B -> 1 B
B -> 0 D
B -> 1 D
D -> EPSILON

Nach Eingabe der Grammatik bietet FLACI den Menüpunkt Konvertieren → rG in NEA an. Hier kann man sich einen endlichen Automaten erzeugen lassen.

Nach der Konvertierung erhält man folgenden Automaten.

Aufgabe 3

Probiere das selbst einmal aus. Wie wird der Automat zur Grammatik erzeugt?

Aufgabe 4

Der resultierende Automat ist kein endlicher Automat im bisherigen Sinne. Welche Besonderheiten fallen auf?

Nichtdeterministische Automaten

Keine Eindeutigkeit

Der folgende Automat zur Erkennung der Sprache $L_{Bin} = {0, 1, 10, 11, 100, 101, 110, 111, 1000, ...}$ ist nichtdeterminstisch in dem Sinne, dass er zulässt, dass von einem Zustand bei derselben Eingabe Übergänge in unterschiedliche Folgezustände möglich sind. Zudem enthält der Automat Zustandsübergänge ohne Eingaben (sog. $\epsilon$-Übergänge).

Automat

Spracherkennung mit nichtdeterministischen Automaten

Spracherkennung mit nichtdeterministischen Automaten funktioniert so ähnlich wie Spracherkennung mit deterministischen Automaten.

Wenn man mit FLACI z.B. das Wort $1001$ eingibt, dann lässt sich die nichtdeterministische Verarbeitung des Eingabewortes anschließend Schrittweise beobachten. FLACI spielt hier alle möglichen Zustandsübergänge durch und zeigt an, welche Zustände erreicht werden.

Zusammenhang zwischen deterministischen und nichtdeterministischen Automaten

FLACI bietet die Möglichkeit an, aus einem nichtdeterministischen Automaten einen deterministischen Automaten zu konstruieren. Hierzu muss man den Menüpunkt konvertieren → NEA in DEA auswählen und den deterministischen Automaten dann generieren.

Aufgabe 5

Probiere das selbst einmal aus. Welches Konzept kann mehr Sprachen abbilden, ist also mächtiger - das Konzept deterministischer Automat oder das Konzept nichtdeterministischer Automat?

Vom regulären Ausdruck zum Automaten

Verarbeitung eines regulären Ausdrucks für Binärzahlen

Reguläre Ausdrücke dienen dazu, Sprachen zu beschreiben. So lässt sich die Sprache $L_{Bin} = {0, 1, 10, 11, 100, 101, 110, 111, 1000, ...}$ mit Hilfe des folgenden regulären Ausdruckes beschreiben: $0|1(0|1)^*$. Nach Eingabe des regulären Ausdrucks bietet FLACI die die Möglichkeit, diesen in einen DEA zu konvertieren.