13.2.3 DEA

Ein Deterministischer Endlicher Automat (DEA) ist wie folgt definiert:

1. Der Automat hat eine feste Anzahl von verschiedenen Zuständen. Diese werden mit einem Kreis dargestellt und enthalten den Namen des Zustands.
2. Genau ein Zustand ist der Startzustand. Dieser wird durch einen kurzen Pfeil gekennzeichnet, dessen Spitze in den Zustand zeigt.
3. Mindestens einer der Zustände ist ein Endzustand. Endzustände werden durch Doppelkreise bzw. Doppelellipsen dargestellt.
4. Der Automat kann durch Eingaben bedient werden. Die Menge der möglichen Eingaben wird Eingabealphabet genannt. Die Elemente des Eingabealphabets nennt man Eingabezeichen. Die Anzahl der verschiedenen Zeichen ist endlich.
5. Bei der Eingabe eines Elements des Eingabealphabets erfolgt stets ein Übergang von einem Zustand 1 in einen Zustand 2. Dieser wird durch einen Pfeil von Zustand 1 nach Zustand 2 dargestellt, wobei über den Pfeil das entsprechende Zeichen des Eingabealphabets geschrieben wird, das den Übergang auslöst. Ein Zustand kann auch auf sich selbst zeigen, was bedeutet, dass der Automat bei der entsprechenden Eingabe im selben Zustand bleibt.
6. Von einem Zustand dürfen keine zwei Pfeile mit der gleichen Markierung auf verschiedene Zustände verweisen, d.h. der Übergang von einem Zustand auf einen anderen muss bei jeder Eingabe eindeutig sein (Deterministisch).

Folgender Automat ist gegeben:

FLACI-Link:

Wir prüfen, ob der gegebene Automat ein deterministischer endlicher Automat (DEA) ist.

• Zu 1.): Es gibt eine feste Anzahl von Zuständen: Z1, Z2, Z3, Z4, ERR
• Zu 2.): Es gibt genau einen Startzustand: Z1
• Zu 3.): Es gibt zwei Endzustände: Z3, ERR
• Zu 4.): Es gibt ein Eingabealphabet mit endlich vielen Zeichen: a, b, c
• Zu 5.): Es gibt bei jedem Zustand einen Übergang für jedes Zeichen des Eingabealphabets, d.h. in der Übergangstabelle gibt es keine Lücken.
• Zu 6.): Es gibt für jeden Zustand immer nur einen Pfeil mit einem Element des Eingabealphabets

Anhand des folgenden Lachautomaten soll die Bedienung und Simulation eines DEA vorgeführt werden. Der Lachautomat soll nur Eingabewörter akzeptieren, welche korrekte Lachwörter sind:

• hi!
• hihi!
• hihihi!
• hihihihi!
• ...

FLACI-Link:

Wir prüfen, ob der gegebene Automat ein deterministischer endlicher Automat (DEA) ist.

• Zu 1.): Es gibt eine feste Anzahl von Zuständen: Z1, Z2, Z3, Z4, ERR
• Zu 2.): Es gibt genau einen Startzustand: Z1
• Zu 3.): Es gibt zwei Endzustände: Z4, ERR
• Zu 4.): Es gibt ein Eingabealphabet mit endlich vielen Zeichen: h, i, !
• Zu 5.): Es gibt bei jedem Zustand einen Übergang für jedes Zeichen des Eingabealphabets
• Zu 6.): Es gibt für jeden Zustand immer nur einen Pfeil mit einem Element des Eingabealphabets

Wir betrachten das Eingabewort "hi!":

Der Automat startet im Startzustand und verarbeitet das erste Zeichen des Eingabeworts: "h" Der Automat wechselt zum nächsten Zustand und verarbeitet das zweite Zeichen des Eingabeworts "i": Der Automat wechselt zum nächsten Zustand und verarbeitet das dritte Zeichen des Eingabeworts "!": Der Automat wechselt zum nächsten Zustand und landet im Endzustand. Da es kein weiteres Zeichen im Eingabewort gibt und der Automat im Endzustand ist, wird das Eingabewort "hi!" akzeptiert.

Falls das Eingabewort abgearbeitet wurde und der Automat nicht im Endzustand ist, wird das Eingabewort nicht akzeptiert.

Öffnen Sie den Automatien in FLACI: FLACI-Link: und klicken Sie in FLACI auf "Simulation".

Geben Sie einige Lach-Eingabewörter ein (auch solche, die nicht korrekt sind, z.B. hihih!) und beobachten Sie, ob das jeweils eingegebene Eingabewort akzeptiert wird.

Ein endlicher Automat, bei welchem von einem Übergang Pfeile auf andere Zustände vorhanden sind, bei welchen bei mehr als einem Pfeil ein gleiches Element des Eingabealphabets zugeordnet ist, ist kein deterministischer Automat. Bei diesen Übergängen entscheidet der Zufall, welcher Übergang gewählt wird und damit kann man nicht vorhersagen, wie der Automat ablaufen wird.

Einen Automaten mit endlichen vielen Zuständen, bei welchem nicht vorhergesagt werden kann, wie die Übergänge zwischen den Zuständen ablaufen werden, nennt man einen Nichtdeterministischen Endlichen Automaten = NEA.