André Vratislavsky

Übungsgruppe vom 02.11.99

Endliche Automaten

Das erste Automatenmodell der Vorlesung ist das der deterministischen endlichen Automaten (dfa).

Wichtige Definitionen (siehe Vorlesung...):

Deterministische endliche Automaten lassen sich durch Zustandsdiagramme beschreiben.
Von den Zuständen ist einer als Startzustand ausgezeichnet und einer oder mehrere als akzeptierende Zustände.
Mit jedem Symbol der Eingabe wird ein Zustand gewechselt, wobei die Zustandüberführungsfunktion definiert, mit welchem Symbol von einem Zustand aus zu welchem Nachfolgezustand gewechselt wird.
Von jedem Zustand aus muß für jedes Eingabesymbol genau ein Nachfolgezustand erreichbar sein (ggfs. auch der Zustand selbst).
Wird nach Abarbeitung eines Wortes ein akzeptierender Zustand erreicht, so ist die Eingabe akzeptiert und somit in der von dem Automaten akzeptierten Sprache enthalten. Ansonsten ist das Wort nicht enthalten.
Siehe auch das Applet für die Konstruktion eines endlichen deterministischen Automaten

Jeder dfa beschreibt eine sog. dfa-Sprache, das ist diejenigen Sprachen, die von diesem dfa erkannt/akzeptiert wird.
Umgekehrt lassen sich bestimmte Sprachen mit dfa's ausdrücken, die sie akzeptieren. Im allgemeinen kann es dabei mehrere dfa's für dieselbe Sprache geben.
 
Sprache: L={w aus {0,1}|...} L(M)
Beschreibung durch: verbale Beschreibung det. endlichen Automaten M

Zunächst wollen wir uns für die dfa-Sprachen interessieren und fragen uns, ob man diese außer mit einer verbalen Beschreibung oder einem dfa auch noch anders charakterisieren kann.

Reguläre Ausdrücke:

Ein zunächst neues Konzept sind die sog. regulären Sprachen (Definition siehe Vorlesung).
Diese werden durch sog. reguläre Ausdrücke als Konstruktionsvorschrift beschrieben.

Jeder reguläre Ausdruck beschreibt nach Definition eine reguläre Sprache.
Umgekehrt lassen sich bestimmte Sprachen mit regulären Ausdrücken notieren.

Eine reguläre Sprache läßt sich also auf zwei Arten beschreiben:
Als Sprache eines regulären Ausdrucks L(a).
Als Menge L mit verbaler Beschreibung der Wörter.
Sprache: L={w aus {0,1}|...} L(a)
Beschreibung durch: verbale Beschreibung Regulären Ausdruck a

Später werden wir sehen, daß die regulären Sprachen genau die Sprachen sind, die durch endliche Automaten erkannt werden.
Damit kann man dann je nachdem, wie es einem besser gefällt, einen dfa oder einen Regulären Ausdruck für ein und dieselbe Sprache verwenden.
 
Sprache: L={w aus {0,1}|...} L(a) L(M)
Beschreibung durch: verbale Beschreibung Regulären Ausdruck a det. endlichen Automaten M

Beispiel:
 
Alphabet A={0,1}
Menge aller Wörter aus A A*={e,0,1,00,01,10,11,000,...}
regulärer Ausdruck a = (0 v (1 (0*) 1))* oder kurz: a = (0 v 1 0* 1)*
Sprache zu a L(a) = {e,0,11,101,1001,00,1001101,...}
äquivalente Sprache L = {w aus{0,1} | w hat die Eigenschaft... }
äquivalenter dfa M = ...

Reguläre Ausdrücke bestehen aus:

'v' bedeutet: Es kann genau eine Altenative verwendet werden.
'*' bedeutet: Es können 0 bis beliebig viele Bestandteile verwendet werden.
Beispiel:
Für a = (0v1)* ist L(a) = {e,0,1,00,01,10,11,000,001,010,011,100,101,...}.

Anmerkung zum Beweis der Gleichheit

Gegeben seien ein regulärer Ausdruck a und eine Sprache L mit verbaler Beschreibung.
Zu zeigen: L=L(a).

Da es sich um Mengen handelt, sind zwei Teilmengenbeziehungn (Richtungen) zu zeigen:

Zeigt man nur eine Teilmengenbeziehung (Richtung), so kann es sein, daß L bzw. a eine viel größere Sprache beschreibt!
Mit einer verbalen Beschreibung lassen sich auch andere, größere Sprachklassen beschreiben!

Entsprechendes gilt für einen dfa M, zu zeigen ist L=L(M).
Dazu zeigt man 2 Richtungen:

oder anders ausgedrückt: Vorgehensweise: (am Beispiel der Sprache der Wörter, die an vorletzter Stelle eine "0" haben.) Zeigt man nur eine Richtung, so kann es passieren, daß z.B. die Maschine mehr Wörter erkennt als von der verbalen Beschreibung definiert!