allgemeiner Mealy-Simulator

Material

Pfad: Startseite / Fächer / Informatik / Material

Autor: mk
08.05.2004 19:03
7180

Automatentheorie

Beispiel für eine Delphi-Realisierung einer Mealy-Maschine

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

"Beispiel 2.18
Sogar wenn das Ausgabe-Alphabet nur aus zwei Symbolen besteht, kann die Mealy-Maschine im Vergleich mit endlichen Automaten - Zustände retten. Betrachten wir etwa die Sprache (0 + 1)*(00 + 11) aller aus Nullen und Einsen bestehenden Zeichenketten, deren letzte beiden Symbole gleich sind. Im nächsten Kapitel werden wir die Werkzeuge entwickeln, die nötig sind, um zu zeigen, daß diese Sprache von keinem DEA mit weniger als fünf Zuständen akzeptiert werden kann. Wir können jedoch eine Mealy-Maschine mit drei Zuständen definieren, die ihren Zustand benutzt, um das letzte gelesene Symbol zu speichern, und die Ausgabe y liefert, wenn die aktuelle Eingabe mit der vorhergehenden übereinstimmt, sowie andernfalls n ausgibt. Die Folge von y und n, die die Mealy-Maschine liefert, entspricht der Folge von akzeptierenden und nicht akzeptierenden Zuständen, in die der DEA während der Eingabe übergeht; die Mealy-Maschine macht jedoch keine Ausgabe bevor nicht eine Eingabe stattgefunden hat, während der DEA auch die [leere] Zeichenkette epsilon verwirft, da der erste Zustand kein Endzustand ist. Die Mealy-Maschine M = ({q0, p0, p1}, {0, 1}, {y, n}, delta, lambda, q0) ist in Abbildung 2.24 gezeigt. Wir benutzen die Markierung a/b für einen Pfeil vom Zustand p in den Zustand q, um anzuzeigen, daß delta(p, a) = q und lambda(p, a) = b ist. Die Antwort von M auf die Eingabe 01100 ist nnyny, wobei die durchlaufene Zustandsfolge q0p0p1p1p0 ist. Beachten Sie, wie sich p0 eine Null und p1 eine Eins merkt. Der Zustand q0 ist der Anfangszustand und "erinnert sich", daß bisher noch keine Eingabe stattfand."

Pfichtenheft

/1/ Das Programm soll objektorientiert nach dem MVC-Muster entwickelt werden.
/2/ Der Automat soll übersichtlich beschrieben werden.
/3/ Das Programm soll einfach an andere Automaten angepasst werden können.
/4/ Eingaben sollen nur aus dem Eingabe-Alphabet möglich sein.
/5/ Zu Kontrollzwecken soll der aktuelle Zustand änderbar sein.
/6/ Ein- und Ausgaben sollen protokolliert werden.

Prototyp

Objektorientierte Analyse und Design

Implementierung

Model

Zunächst soll die TAutomat-Klasse besprochen werden. Wie man sieht, werden selbstdefinierte Aufzähltypen TZustand, TEingabe, TAusgabe verwendet. Diese Typen legen die Zustände, das Eingabe- und das Ausgabe-Alphabet fest. Die Übergangs- und die Ausgabefunktion sind ebenfalls außerhalb der Klasse in Array-Konstanten festgelegt.

const
  { 0. Automatenname eintragen }
  automatname = 'Mealy-Automat, Hopcroft/Ullman, S.45';
type
  { 1. Zustandsmenge, Eingabe- und Ausgabealphabet anpassen                }
  TZustand = (q0,p0,p1);
  TEingabe = (e0,e1);
  TAusgabe = (an,ay);
const
  { 2. Startzustand eintragen }
  startzustand = q0;
  { 3. Klartextentsprechungen eintragen                                    }
  zText : array[TZustand] of string =
          ('q0','p0','p1');
  eText : array[TEingabe] of string =
          ('0','1');
  aText : array[TAusgabe] of string =
          ('n','y');
  { 4a. Automatentafel eingeben, auf Zeilen und Spalten achten              }
  fue   : array[TZustand,TEingabe] of TZustand =
          ((p0,p1),
           (p0,p1),
           (p0,p1));
  { 4b. Automatentafel eingeben, auf Zeilen und Spalten achten              }
  fa    : array[TZustand,TEingabe] of TAusgabe =
          ((an,an),
           (ay,an),
           (an,ay));

Damit ist die TAutomat-Klasse universell für alle Transduktoren. Zur Realisierung eines anderen Automaten sind lediglich die rot gekennzeichneten Stellen zu ändern, an der eigentlichen Automaten-Klasse ändert sich nichts.
TAutomat hält den aktuellen Zustand, die gemachte Eingabe und die letzte Ausgabe fest. Außer einfachen Set- und Get-Methoden und einem erweiterten Konstruktor gibt es nur die Methode verarbeiteEingabe, die auch verblüffend einfach ist:

constructor TAutomat.create;
begin
  inherited create;
  zustand := startzustand;
end;
...
procedure TAutomat.verarbeiteEingabe;
begin
  ausgabe := fa[zustand,eingabe];
  zustand := fue[zustand,eingabe];
end;

View/Control

Die grafische Benutzeroberfläche ist völlig unabhängig vom speziellen Automaten, dh. an der Unit uGUI muss nichts geändert werden. Perfekte Wiederverwertung!

Interessant ist die Verwendung von ComboBoxen für Zustand, Eingabe und Ausgabe.
Die auswählbaren Items werden beim Programmstart aus den entsprechenden Arrays in die ComboBoxen eingelesen. Damit ist sichergestellt, dass für Eingaben und Zustände nur erlaubte Werte ausgewählt werden können. Die Auswahlliste bei der Ausgabe dient der Information über das Ausgabe-Alphabet, das hier eingesehen werden kann.
Details für Belegung und Auslesen der Auswahlisten/ComboBoxen finden sich in folgenden Quelltext-Auszügen.

...
// Eingabealphabet in ComboBox eintragen
  for e := Low(TEingabe) to High(TEingabe) do
    cbEingabe.Items.Add(eText[e]);
  cbEingabe.ItemIndex := 0;
...
procedure TForm1.bVerarbeiteClick(Sender: TObject);
begin
  if (cbZustand.ItemIndex <> -1) and (cbEingabe.ItemIndex <> -1)
  then
  begin
    automat.setZustand(TZustand(cbZustand.ItemIndex));
    automat.setEingabe(TEingabe(cbEingabe.ItemIndex));
    automat.verarbeiteEingabe;
    mEingaben.Lines.Add(eText[automat.getEingabe]);
    cbZustand.ItemIndex := Ord(automat.getZustand);
    cbAusgabe.ItemIndex := Ord(automat.getAusgabe);
    mAusgaben.Lines.Add(aText[automat.getAusgabe]);
  end;
end;

Download: mealy.zip

Test

Durch die Möglichkeit, den Zustand zu setzen, kann man den Automaten bequem völlig durchtesten. Man geht Zustand für Zustand durch, setzt die entsprechenden Eingaben und kontrolliert den Folgezustand sowie die Ausgabe.
Fehleingaben, die man in den ComboBoxen versucht, werden durch Kontrollen auf den ItemIndex -1 (nicht ausgewählt) abgefangen.