Datenverarbeitende Systeme:
Kapitel 3: Sprachen endlicher Automaten

3.1 Das Pumping-Lemma

Wir wollen als nächstes eine Methode finden, um zu zeigen, ob eine Sprache regulär ist oder nicht. Der Nachweis, dass eine Sprache nicht(!) regulär ist, gelingt uns mit Hilfe des Pumping-Lemmas. Dieses lautet wie folgt:

Leider lässt sich nur zeigen, dass eine Sprache L nicht regulär ist, wenn das Pumping-Lemma nicht gilt. Wir gehen dazu wie folgt vor: Wähle zunächst ein n beliebig und ein Wort x mit einer Länge >= n. Zerlege x so, dass obige Bedingungen für u, v und w gelten. (ACHTUNG: Nicht jede Zerlegung ist geeignet zur Beweisführung. Wie x zu zerlegen ist, ist je nach Sprache verschieden!) Man wähle jetzt ein i aus den natürlichen Zahlen (mit Null) so, das die Erweiterung uvⁱw nicht mehr in L liegt. Dann ist L nicht regulär.

Beispiel:

L={a^kb^k}: Wir wählen n = 2 und ein Wort aaabbb. Wir zerlegen u = a, v = aa, w = bbb. Wir wählen i = 3 -> x = a aa aa aa bbb. Dieses Wort liegt eindeutig nichtmehr in L.

3.2 Operationen auf Sprachen

Auf reguläre Sprachen REG(X) sind die Operationen Komplement, Vereinigung, Komplexprodukt und Klenee-Abschluß anwendbar. REG(X) ist bezüglich dieser Operationen abgeschlossen.

1. Komplement
Ein endlicher deterministischer Automat Â, der das Komplement von A akzeptiert, erkennt alle Nicht-Ende-Zustände von A als Endezustände und umgekehrt. Ich verwende im Folgenden den Operator ^. Normalerweise verwendet man den Komplementstrich über dem Zeichen.

2. Vereinigung
Aus zwei endlichen Automaten beliebiger Art können wie einen Automaten machen, der die Vereinigung beider Sprachen akzeptiert, indem wir beide Automaten nebeneinander zeichenen und als einen Automaten definieren. Dieser Automat ist auf jeden Fall nicht deterministich! Ich verwende als Operator das + Zeichen. Zum Beispiel: {a} + {b} = { a, b }.

3. Komplexprodukt
Aus zwei Automaten können wir ein Komlexprodukt bilden. Der neue Automat erkennt dann das Pdrodukt beider Automaten. Als Operator dient der Multiplikationspunkt, den man auch werglassen kann. Zum Beispiel: A = { a } { b } = { ab }

4. Klenee-Abschluß
Der Klenee-Abschluss A* bezeichnet alle möglichen Kombinationen, die aus A entnommen werden können. Als Operator verwendet man das * Zeichen (Klenee-Operator). Zum Beispiel: { a }* = { aⁱ } i aus N mit Null; { ab }* = { (ab)i } i aus N mit Null; ( {a} , {b} )* = { aⁱb^j } i,,j aus N mit Null; ( {b}, {ab} )* = { bⁱab^j1ab^j2...ab^jk } i,j,k aus N mit Null!

Jede Einelementige Menge {x} ist regulär. Jede Menge M, die sich aus {x} durch die obigen 4 Operationen zusammenbauen lässt, ist regulär. Zu jeder regulären Menge M gibt es einen endlichen Ausdruck, durch den sich ein endlicher Automat zeichnen lässt. Jeder endliche Automat erkennt eine reguläre Sprache. Die Folge ist beliebig vertauschbar.

Aus einer regulären Sprache kann ein Automat erstellt werden, umgekehrt kann zu jedem Automaten eine reguläre Sprache gefunden werden, die der Automat erkennt.