Material OOP Grundlagen Delphi Software-Technik Bonsai Digitaltechnik Ereignisse Grafik UML Netze Fischertechnik Tipps Werkzeuge Literatur Automaten Sprachen Datenbanken XML Prolog Berechenbarkeit
Pfad: Startseite / Fächer / Informatik / Material
Autor: mk
08.05.2004 11:24
2934
endliche Automaten

Beispiel eines deterministischen endlichen Automaten (DEA)

aus Hopcroft/Ullman, Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie, S.16:

"Beispiel 2.1
Das Transitionsdiagramm eines EA ist in Abbildung 2.2 dargestellt. Der Anfangszustand qo ist durch den mit "Start" markierten Pfeil angegeben. Es gibt einen Endzustand, in diesem Fall ebenfalls qo, der durch den doppelten Kreis markiert ist. Der EA akzeptiert alle aus Nullen und Einsen bestehenden Zeichenketten, in denen sowohl die Anzahl der Nullen als auch die Anzahl der Einsen gerade ist. Um dies zu sehen, stelle man sich eine "Kontrolle" vor, die im Diagramm von Zustand zu Zustand wandert. Die Kontrolle startet im Zustand qo und muß auch im Zustand qo enden, wenn die Eingabe-Folge akzeptiert werden soll. Jede 0-Eingabe veranlaßt die Kontrolle, die horizontale Linie a-b zu überqueren, während eine 1-Eingabe dies nicht tut. Also befindet sich die Kontrolle genau dann in einem Zustand oberhalb der Linie ab, wenn die bis dahin gesehene Eingabe eine gerade Anzahl von Nullen enthält. Ebenso befindet sich die Kontrolle genau dann links der vertikalen Linie c-d, wenn die Eingabe eine gerade Anzahl von Einsen enthält. Also befindet sich die Kontrolle genau dann im Zustand qo, wenn es in der Eingabe sowohl eine gerade Anzahl von Nullen als auch eine gerade Anzahl von Einsen gibt. Beachten Sie, daß der EA seine Zustände nur benutzt, um die Gleichheit, bzw. Ungleichheit der Anzahl der Nullen und der Anzahl der Einsen zu speichern - nicht deren genaue Zahl, was eine unendliche Anzahl von Zuständen erfordern würde."

Prototyp eines Programms zum "allgemeinen DEA" am Beispiel

Download des "allgemeinen DEA-Simulators"

DEA.zip (Delphi7-Quellen)

Automatenbeschreibung in der Include-Datei hop17.aut

const
  { 0. Automatenname eintragen                 }
  automatname = 'DEA, Hopcroft/Ullman, S.17';
type
  { 1. Zustandsmenge, Eingabealphabet anpassen }
  TZustand = (q0,q1,q2,q3);
  TEingabe = (e0,e1);
const
  { 2. Startzustand eintragen                  }
  startzustand = q0;
  { 3. Endzustände eintragen                   }
  Endzustaende : set of TZustand = [q0];
  { 4. Klartextentsprechungen eintragen        }
  zText : array[TZustand] of string =
          ('q0','q1','q2','q3');
  eText : array[TEingabe] of string =
          ('0','1');
  { 5. Automatentafel eingeben                 }
  fue   : array[TZustand,TEingabe] of TZustand =
          ((q2,q1),
           (q3,q0),
           (q0,q3),
           (q1,q2));