DEA


Deterministische Endliche Automaten

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).

Beispiel 1:

Folgender Automat ist gegeben:

graph bsp 1

tabelle bsp 1

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

Aufgabe 1:

In einem Computer gibt es auf Hardware-Ebene Übergänge zwischen Zuständen, die mit nur zwei Eingaben ausgelöst werden: 0 und 1.

A1.1: Denken Sie sich einen deterministischen endlichen Automaten (DEA) aus, der nur eine Folge aus 1 und 0 akzeptiert die auf "10" enden, also nur dann im Endzustand landet, wenn das Eingabewort auf "10" endet.

A1.2: Prüfen Sie die Funktion des DEA mit folgenden Eingabeworten:

  • 1110110 (sollte im Zustand "Akzeptiert" = "AKZ" enden)
  • 1100001 (sollte nicht im Zustand "Akzeptiert" = "AKZ" enden)
  • 0100011 (sollte nicht im Zustand "Akzeptiert" = "AKZ" enden)
  • 0001100 (sollte nicht im Zustand "Akzeptiert" = "AKZ" enden)

A1.3: Prüfen Sie die Funktion des DEA im Simulator mit einer Vielfalt an Eingabeworten, die auf "10" enden.

Mögliche Lösung: hier klicken...

Aufgabe 1 Simulation 1 Simulation 2 Simulation 3 Simulation 4 FLACI-Link:


Aufgabe 2:

A2.1: Denken Sie sich einen deterministischen endlichen Automaten (DEA) aus, der nur dann eine Folge des Buchstabens "b" akzeptiert, wenn diese aus einer Anzahl von Buchstaben besteht, welche durch 3 teilbar ist.

A2.2: Testen Sie den Automaten mit mindestens 10 verschieden langen Eingabeworten.

Mögliche Lösung: hier klicken...

Aufgabe 2 Simulation 1 Simulation 2 FLACI-Link:


NEA

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.

Aufgabe 3:

Denken Sie sich einen NEA aus und realisieren Sie diesen mit FLACI.

Mögliche Lösung: hier klicken...

Aufgabe 3 FLACI-Link: