|
|
I-PROGR3 WS03 - PROGRAMMIEREN3 - Vorlesung mit Übung
|
In der bisherigen Vorlesung sind in der ersten Phase einige zentrale Konzepte des objektorientierten Programmierens am Beispiel des UML-Standards präzisiert und an Beispielen illustriert worden. In der zweiten Phase wurden die sehr verbreiteten und mächtigen Werkzeuge flex und Bison zur Syntaxanalyse vorgestellt und gezeigt, wie sie sich im Rahmen von C++ und in Verbindung mit vorhandenen Klassen integrieren lassen. In dieser dritten Phase nun soll am Beispiel des Damespiels ferner gezeigt werden, wie sich das aus der theoretischen Informatik bekannte Konzept des Automaten für die Lösung einer Aufgabe benutzen lässt und, natürlich, wie dies mit objektorientierten Mitteln geschehen kann.
Zu diesem Zweck werden wir den bisherigen Use Case geringfügig abändern. Statt, wie bislang, anzunehmen, dass zwei menschliche Spieler abwechselnd Züge eingeben, nehmen wir jetzt an, dass nur einer der beiden Spieler, nämlich der weisse Spieler, ein menschlicher Spieler ist, und der schwarze Spieler wird von unserem Programm simuliert. Diese geringfügige Änderung erlaubt es uns, eine Reihe von Themen aus der theoretischen Informatik und aus der Vorlesung zu Algorithmen und Datenstrukturen einzubeziehen; zugleich deuten sich Themen an, die in die Richtung Wissensrepräsentation, Spieltheorie und Lernen gehen.
Modifizierter Use Case mit Mensch und Computer
Der Use Case entspricht dann in etwa der Situation, die man von den vielen Schachprogrammen her kennt: der menschliche Spieler führt die weissen Steine. Wenn er das Programm gestartet hat, kann er das Spiel eröffnen; automatisch wird er den weissen Steinen zugeordnet. Er kann dann einen Zug ausführen, der am Brett angezeigt wird. Dann muss er warten, bis der Computer --also unser Programm- eine Antwort berechnet und dem Hauptprogramm übermittelt hat. Sobald dies geschehen ist, wird auch dieser Zug angezeigt. Dann kann Weiss wieder ziehen, so lange, bis entweder das Spiel beendet ist oder aber der weisse Spieler die Lust verliert und das Spiel einfach beendet.
Aus objektorientierter Sicht liegt es nahe, den 'neuen' schwarzen Spieler durch eine eigene Klasse zu repräsentieren. Diese neue Klasse 'automatischer (schwarzer) Spieler' interagiert dann mit der Klasse 'world'. Sinnvollerweise konzipiert man die neue Klasse 'automatischer Spieler' so allgemein, dass sie sowohl für Schwarz als auch für Weiss eingesetzt werden könnte.
Klassen zum modifizierten Use Case mit Mensch und Computer
Wenn man die Klassen so anordnet, wie dies im obigen Schaubild geschehen ist, dann stehen diese Klassen 'gleichberechtigt nebeneinander'; keine kann Methoden der anderen direkt aufrufen. Man benötigt ein Usage-Programm, das diese beiden Klassen 'integriert'. Eine Alternative würde darin bestehen, die Klasse 'auomatic_player' in die Klasse 'world' so zu integrieren, dass der automatische Spieler ein Teil der Klasse 'world' wäre. Dann könnte die Klasse 'world' die Klasse 'auomatic_player' in eigener Regie aufrufen. Wir belassen es zunächst einmal bei der aktuellen Anordnung; dadurch bleibt die Klasse 'world' überschaubarer.
Sequenzdiagramm zum modifizierten Use Case mit Mensch und Computer
Ein menschlicher Spieler kann ein Programm über die Klasse 'world' starten. Als nächstes muss er dann angeben, welche Rolle die Klasse 'automatic_player' übernehmen soll. Ab dann tritt eine Schleife in Kraft, in der abwechselnd der menschliche Spieler und der 'automatic_player' Züge generieren. Nach jedem Zug wird die Spielstellung für den weissen Spieler angezeigt. Das Spiel kann jederzeit von dem menschlichen Spieler beendet werden.
Im weiteren Verlauf soll nun diese Klasse 'automatic_player' weiter ausgearbeitet werden.
Im folgenden soll der Frage nachgegangen werden, ob man den neu eingeführten automatischen Spieler durch einen Automaten repräsentieren kann, und falls ja, durch welchen Automaten.
Dazu muss man wissen, was ein Automat ist? Ein mögliche Antwort ist die, dass ein Automat ein Input-Output-System mit internen Ressourcen Q und einer Systemfunktion F ist, die den Input INP in Abhängigkeit von den internen Ressourcen Q auf den Output OUT abbildet: F : INP x Q ---> OUT. Diese Formulierung ist natürlich noch nicht sehr aussagekräftig. Um ihr mehr 'Bedeutung' zu verleihen kann man versuchen, Automaten durch ihre Leistung zu charakterisieren, z.B. hinsichtlich der Eigenschaft, welche Art von formalen Sprachen durch einen Automaten erkannt werden können. Entsprechend der Hierarchie der formalen Sprachen erhält man dann auch eine Hierarchie der Automaten; die Taxonomie, nach der in dieser Hierarchie die Automaten angeordnet wedren, ist dann die Komplexität der Sprachen, die erkannt werden. Die Komplexität der Sprachen wiederum wird beschrieben durch den Typ der Grammatik, die diese Sprachen beschreibt. Eine Übersicht über eine grobe Einteilung der Hierarchie auf der Basis der sogenannten Chomsky-Hierarchie findet sich hier. Wir werden uns im folgenden auf zwei Typen von Automaten konzentrieren: auf endliche Automaten --das sind die einfachsten-- und auf die Turingmaschine, das ist der stärkste bekannte Typ überhaupt.
Wir wollen die Frage, ob man den neu eingeführten automatischen Spieler durch einen Automaten repräsentieren kann, hier in zweifacher Form stellen: (i) Reicht ein endlicher Automat? bzw. (ii) Was bietet uns eine Turingmaschine?
Fragen wir zuerst, inwieweit ein endlicher Automat unseren automatischen Spieler repräsentieren kann.
Zunächst benötigen wir eine etwas genauere Definition eines endlichen Automaten. Eine Übersicht über die wichtigsten Typen endlicher Automaten findet hier. Aus dieser Liste von endlichen Automaten wählen wir für unsere Zwecke den MEALY-Automaten aus. Der mealy-Automat ist, wie man erkennen kann, ein spezieller Fall der allgemeinen Fassung einer Finite state Machine (FSM).
FSM(a) gdw a = < < Q, E, Ti, To, {§}, {q0 } >, < P > >
mit
Q:= endliche nichtleere Menge von Zuständen
E := Menge der Endzustände; E C Q & E != 0
Ti:= endliches Eingabe-Alphabet; |Ti| > 0
To:= endliches Ausgabe-Alphabet; kann leer sein
B = Ti u {§}; das endliche Bandalphabet
§ := das leere Zeichen
q0 := der Anfangszustand; q0 in Q
P ist das Programm des endlichen Automaten t und es gilt
P: (Q -E) x B --->
Q x To
MEALY(a) hat die Programmfunktion PMEALY: Q x B ---> Q x To
Der Mealy-Automat ist also ein endlicher Automat a, der einen Input B besitzt und in Abhängigkeit von seinen internen Zuständen Q in einen neuen Zustand übergeht und dabei einen Output To erzeugt.
Was bedeutet dies für unseren Anwendungsfall?
Unser Anwendungfall ist dadurch gekennzeichnet, dass der automatische Spieler als Input die aktuelle Spielstellung bekommen soll und als Output seinen nächsten Zug angeben soll.
Automatischer Spieler als Automat
Dieses Szenario kann man weiter verallgemeinern, indem man sich das Board zerlegt denkt in einen String von Zeichen, die die Spielstellung repräsentieren, und der Antwortzug ebenfalls als eine Zeichenkette. Noch allgemeiner, man kann sich vorstellen das unser Automat, der den automatischen Spieler repräsentieren soll, für den Input ein Input-Band von links nach rechts lesen kann, und dann seine Antwort auf einem anderen Output-Band von links nach rechts ausdruckt.
Automatischer Spieler als Automat mit Input-Output-Bändern
Ein endlicher automat in Gestalt eines Mealy-Automaten würde also als Input eine Bandinschrift bekommen, die von links nach rechts eine komplette Spielstellung beinhalten würde und der dann, nach diversen internen Beerechnungen, auf sein Outputband den von ihm berechneten nächsten Zug schreiben würde.
Die interessante Frage, die sich hier für uns stellt, ist die, ob die internen Berechnungsmöglichkeiten eines Mealy-Automaten ausreichen, um einen interesanten Zug zu finden.
Bevor wir diese Antwort beantworten, seien hier die zwei wichtigsten Darstellungsmödlichkeiten für einen Mealy-Automaten --und damit auch eines endlichen Automaten-- erinnert, die wir benutzen können. Das eine ist eine graphische Notation --der Mealy Automat als Graph--, die andere ist eine Tabelle.
Beginnen wir mit der Tabelle.
Die Systemfunktion eines Mealy-Automaten lautete:
PMEALY: Q x B ---> Q x To
d.h. wenn ein Zustand q aus Q und eine Inschrift b aus B gegeben ist, dann muss der Automat wissen, in welchen Zustabnd q' aus Q er als nächstes zu wechseln hat und welches Element b' aus To er auf das Output-Band zu schreiben hat. Allgemein gilt, dass man eine Funktion mit endlich vielen Werten als Tabelle hinschreiben, so auch hier. Man könnte die Übergangsfunktion PMEALY also z.B. schreiben:
<q0, b0.1, q'0, b'0.1 >
.....
<q0, b0.k, q'k, b'0.k >
.....
<qi, bi.1, q'i, b'i.1 >
.....
<qi, bi.m, q'm, b'i.k >
.....
<qn, bn.1, q'n, b'n.1 >
.....
<qn, bn.r, q'n, b'n.r >
Anders gesprochen, wenn der Automat im Zustand q0 den Input b0.1 auf dem Input-Band vorfindet, dann wird er in den Zustand q'0 übergehen und die Antwort b'0.1 auf das Band schreiben. usw. M.a.W. der Mealy-Automat ist vollständig definiert; für jedes Ereignis ist genau eine Antwort festgelegt. Eine graphische Darstellung dieser Sachverhalte ist unmittelbar ableitbar:
Graphische Repäsentation eines Mealy-Automaten
Die Knoten des Graphen repräsentieren Zustände des Mealy-Automaten, die Ursprünge der Kanten repräsentieren den jeweiligen Inhalt des Input-Bandes, und die Notation in der Mitte der Kante repräsentiert die Antwort des Automaten bei diesem Input. Die Kante endet in dem neuen Nachfolgezustand.
Während die graphische Notation für das intuitive Verständnis direkter zugängtlich sind, ist die Tabellenform geeigneter für die Behandlung innerhalb eines Computers.
Hier ist ein einfaches Beispiel für einen Mealy-Automaten, der als Input 1-stellige Dezimalzahlen bekommt und diese in römische Ziffern konvertiert:
<1,0, 1, 0 >
<1, 1, 1, 1 >
.....
<1,5, 1, v >
<1, 6, 1, vi >
.....
<1,8, 1, iix >
<1, 9, 1, ix >
Graphische Repäsentation eines Mealy-Automaten der 1-stellige Dezimalzahlen in römische Ziffern konvertiert
Gut, jetzt wissen wir, was ein Mealy-Automat ist, aber was kann er für die Aufgabe leisten, einen automatischen Spieler zu simulieren?
Betrachten wir seine Aufgabenstellung näher.
Aufgabe des automatischen Spielers
Ein automatischer Spieler bekommt als Input die aktuelle Spielstellung und muss dann versuchen, den bestmöglichen Zug in dieser Stellung zu berechnen. Dazu muss er in der Lage sein, (i) bestimmen zu können, welche Züge sind überhaupt möglich. Kann diese Aufgabe gelöst werden, stellt sich (ii) die Frage, welcher der möglichen Züge ist der beste Zug?
Schauen wir uns das an.
Um zu wissen, welcher Zug möglich ist, muss man wissen, wie kann man überhaupt Züge im Spiel darstellen? Eine einfache Möglichkeit, dies zu tun, ist eine algebraische Darstellung der Spielstellungen und der Züge.
Algebraische Notation
Ein schwarzer Spieler zieht zunächst 'von hinten' nach 'vorne', d.h. von der Zeile 8/7/6 zu den Zeilen 3/2/1. Für einen normalen Zug stehen dabei nur zwei Möglichkeiten zur Verfügung, entweder 'schräg links vorne' oder 'schräg rechts vorne'. Benutzt man eine algebraische Notation, dann kann ein schwarzer Spieler also von der Linie i nur zur Linie i-1 ziehen, und zwar ausgehend von der Spalte j entweder nur nach j-1 ('links') oder j+1 ('rechts').
Ein solcher Zug ist möglich, wenn das Zielfeld 'frei' ist, d.h. kein anderer Spielstein sich dort befindet. Ein eigener Spielstein blockiert; ein fremder Spielstein kann übersprungen werden, wenn das Feld dahinter frei ist.
Mit Hilfe solch einer Notation könnte man also, ausgehend von einem Startfeld, alle Felder systematisch absuchen und fragen (i) wo steht ein eigener Stein, und dann fragen (ii) kann dieser eigene Stein entweder einen normalen Zug machen oder einen gegnerischen Stein überspringen.
Solche Überlegungen sind zwar --verglichen mit den tatsächlichen strategischen Überlegungen beim Damespiel-- noch sehr einfach, aber sie bilden die Basis für weitere komplexere Überlegungen.
Als nächstes wäre noch zu klären, was der beste Zug sein sollte. Diese Frage ist weder schnell noch einfach zu beantworten, da hier eine Vielzahl von Eigenschaften einfliessen können.
Für die folgenden Überlegungen werden folgende --sehr vereinfachende-- Prinzipien formuliert, um den besten Zug zu ermitteln:
Einen gegnerischen Stein schlagen ist besser als nur einen Zug machen
Umso mehr gegnerische Steine in einem Zug geschlagen werden können, um so besser
Von zwei Zügen ist derjenige besser, der weiter nach vorne führt (i'1 < i'2)
Von zwei möglichen Zügen ist derjenige besser, der mehr an den Rand führt (j' ist näher an 1 oder näher an 8).
Nach diesen Vorüberlegungen kann man sich jetzt überlegen, wie denn ein solches Konzept eines automatischen Spielers als Mealy-Automat mit objektorientierten Konzepten repräsentierbar und realisierbar wäre. Unser Interesse liegt darin, die Klasse 'automatic_player' auf unterschiedliche Weise zu realisieren. Und zwar wollen wir drei Konzepte ausprobieren: den 'automatic_player' als Mealy-Automat, als Turingmaschine und mit Hilfe von sogenannten Taskgraphen (siehe Bild):
Gesamtprojekt Programmieren 3
Diese unterschiedlichen Realisierungen werden jeweils als Klassen konzipiert, die der Klasse 'automatic_player' als vorgegebener Datentyp zur Verfügung stehen.
Bevor wir einen Mealy-Automaten direkt als Klasse in die Klasse automatic_player integrieren, bauen wir zunächst einen Simultor, mit dem wir jeden Mealy-Automaten simulieren können. Die Grundstruktur eines Simulators fuer Mealy-Automaten ist sehr einfach (siehe Bild):
Simulator für Mealy-Automat
Die Menge der Zustände eines Mealy-Automaten (die 'Maschinentafel', das 'Mealy-Programm') wird als Textatei mit Endung .mealy eingelesen. Dann wird schrittweise der Input von links nach rechts gelesen und entsprechend den Anweisungen im Programm abgearbeitet. Der jeweilige Output wird auf die Ausgabe geschrieben. Dies geschieht so lange, bis einer der Endzustände des Mealy-Programms erreicht wird.
Als 'Format' für die Mealy-Programmdateien .mealy soll gelten, dass in der ersten Zeile die Nummern aller Endzustände E in geschweiften Klammern aufgeführt werden. Danach folgt die endliche Menge der Zustände Q, wobei jeder endliche Zustand die Form hat:
< Akt.Zustand, Gelesenes Token, zu schreibendes Token, Folgezustand >
Die folgenden Diagramme illustrieren die Arbeitsweise eines Mealy-Automaten und wie man ihn simulieren könnte.
Der Programmzähler PC beginnt bei Zustand 1. Als erstes wird das Zeichen '0' gelesen. Im Zustand 1 heisst dies, dass auf dem Ausgabeband das Zeichen '0' gschrieben werden soll. Der Nachfolgezustand ist wieder 1.
Simulator Zustand 1
Im nächsten Schritt wird von der Eingabe die '2' gelesen; dies führt zur Ausgabe 'ii', usw.
Simulator Zustand 2
Sobald dann die Eingabe '+' gelesen wird, geht der Automat in den Folgezustand '2' über, d.h. PC=2. Sobald der Automat im Zustand 2 die Eingabe '+' liest, wird er in den Zustand 3 übergehen, PC=3; da '3' ein Endzustand ist, wird der Automat an dieser Stelle anhalten.
Für die weiteren Schritte ist es nun notwendig, zu klären, wie man diese unterschiedlichen Anforderungen in eine Implementierung umsetzen kann. Das folgende Schaubild liefert einige mögliche Eckwerte.
Designüberlegungen zum Mealy-Simulator
Grundsätzlich ist klar, dass der Mealy-Automat mit einem Programm geladen werden muss und über Input-Output Fähigkeiten verfügen soll. Wie das Schaubild zeigt, gibt es hier aber unterschiedliche Lösungsmöglichkeiten:
Die Programmdatei wird von dem Usage-Programm geladen und evtl. vorverarbeitet.
Der Mealy-Automat lädt selbst die Programmdatei
Für Variante (1) würde sprechen, dass die Usage-Datei eine Analyse der Textdatei vornimmt und die Ergebnisse in eine geeignete Datenstruktur packt, die dann dem Mealy-Automat übergeben wird. Folgende Varianten wurden in der Diskussion für eine mögliche Lösung bislang genannt:
Die Programmdatei wird von dem Usage-Programm geladen und evtl. vorverarbeitet.
Eine Mealyprogramm-Datei nnn.mealy wird mittels der Funktion yylex() geladen und gleich analysiert. Die Analyseergebnisse werden in eine Datenstruktur (Array) geschrieben. Dieser Array wird dann an den mealy-Automaten übergeben. Nachteil: die Verwendung von yylex() schliesst typische C++-Datenstrukturen aus, z.B. dynamische Arrays. Auch ist die Mischung von C- und C++-I/O-Funktionen unschön.
Man verzichtet auf yylex() und liest die Daten mittels eigener Funktionen in eine Datenstruktur vom Typ Liste ein; ein Listenelement ist eine eigene Struktur mit allen Informationen, die einen Automatenzustand repräsentieren wie z.B. 'aktueller Zustand', 'aktuell gelesenes Zeichen', 'Folgezustand', 'zu schreibendes Zeichen'. Nachteil u.a.: beim Suchen nach passenden Automatenzuständen muss immer die gesamte Liste durchlaufen werden.
Analog wie im Beispiel mit der Liste; man verwendet stattdessen aber eine Datenstruktur vom Typ vector<EIGENER STRUCT> ein. Wie bei der Liste hat man als Elemente des Vektors eine eigene Struktur. Im Gegensatz zur Liste, kann man bei einem Vektor direkt auf jedes Element zugreifen, allerdings muss man wissen, welches Element einschlägig ist; dies geht nicht ohne Suche ab.
Der Mealy-Automat lädt selbst die Programmdatei
Ein anderer Vorschlag bestand darin, dass der Mealy-Automat das Programm selber einlädt, allerdings in eine Datenstruktur C++-String. Ein String ist sehr flexibel. Verlangt aber auch die Implementierung einer eigenen Suchfunktion.
Ein weiterer Vorschlag brachte die mächtige C++-Datenstruktur 'map' aus der STL ins Spiel. Die Datenstruktur map --intern ein sogenannter Red-Black-Tree, ein balanzierter binärer Suchbaum-- arbeitet mit zwei Elementen: einem frei definierbaren Schlüssel ('key') und einem frei definierbaren Wert ('value'). Anhand des Schlüssels kann man entweder einen Eintrag erzeugen oder einen vorhandenen Eintrag finden. Der Wert dieses Eintrags wird dann eben von dem Wert gebildet. Im präsentierten Vorschlag wurde der Wert als eine Struktur realisiert, die das zu schreibende Zeichen und den Nachfolgezustand enthält. Der Schlüssel enthält dann den aktuellen Zustand und das gelesene Zeichen. Diese Lösung hat mehrere Vorteile: (i) die Suchwege sind gegenüber Vektoren und Listen im Durchschnitt günstiger; (ii) die Implementierung eigener Suchfunktionen entfällt, da diese Teil der Datenstruktur map sind; (iii) das Parsen der mealy-Programmdatei ist vergleichsweise einfach.
Ein ähnlicher Vorschlag mit der Datenstruktur map war auch in der Übungsgruppe A diskutiert worden; allerdings war dort angenommen worden, dass der Wert keine Struktur ist, sondern einfach nur ein String mit Folgezustand und Ausgabezeichen; natürlich müsste dann dieser Wert im konkreten Fall dann 'interpretiert' werden. Welche der beiden Varianten effektiver ist, das müsste im konkreten Fall untersucht werden.
Diese Überlegungen beschreiben sicher nicht alle Möglichkeiten. Sie zeigen aber schon, wie vielfältig die Möglichkeiten sind. Eine Analyse der verschiedenen Möglichkeiten mit einer Bewertung ist daher notwendig, bevor die endgültige Implementierung vorgenommen wird.
Ein möglicher Entwurf für das Aktivitätsdiagramm des Usage-Programms des Mealy-Simulators könnte das folgende sein:
Aktivitätsdiagramm des Simulator-Usage-Programms
Es folgt jetzt eine Implementierung --die allerdings noch nicht vollständig ist--, in der die Variante demonstriert wird, bei der yylex() die Programmdatei einliest, analysiert, und in eine Datenstruktur packt.
Das Usage-Programm ist wie folgt aufgebaut:
//******************************++
//
// mealy_usage2.cpp
//
// COMPILATION:
// (i) flex progread.l ==> lex.yy.c
// (ii) g++ -o usage2b usage2.cpp mealy.cpp lex.yy.c -lfl
//
//******************************************
#include "mealy.h"
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
int main(){
extern const int dim1, dim2, dim3;
extern int yylex();
extern char table[][4][20];
extern int endstates[];
extern int counter;
extern int counter2;
string file_name, tmp_name, input_buffer;
const string suffix ("mealy");
FILE *dz;
FILE *yyin = stdin; // yylex() liest von yyin; die Datei muss darauf umgeleitet werden
char dname[40]; // Feld fuer Dateinamen mit maximal moeglicher Länge */
int i,j;
char c;
mealy m1; // Ein Mealy-Automat
// BENUTZER SOLL DATEINAMEN FUER MEALY-PROGRAMMDATEI EINGEBEN
cout << "WELCHE MEALY-PROGRAMMDATEI SOLL GELADEN WERDEN (ohne Suffix .mealy) ?\n" << endl;
cin >> tmp_name;
file_name = tmp_name + '.' + suffix;
cout << "DATEINAME : " << file_name << endl;
strcpy(dname,file_name.c_str());
// PROGRAMM-DATEI OEFFNEN UND EINLESEN
if( (dz = freopen(dname,"r",yyin)) != NULL )
{
printf("yylex() beginnt\n");
yylex();
fclose(dz);
}
else{
fprintf(stderr, "Datei %s kann nicht geoeffnet werden\n",dname);
exit(1);
}
//*************AUSLESEN DES ARRAYS VOR UEBERGABE AN MEALY-AUTOMAT***********************
cout << "KONTROLLAUSDRUCK MEALY-PROGRAMM" << endl;
cout << "--------------------------------------------" << endl;
for(i=0; i<counter2+1; i++){ printf("%d = %d\n",i,endstates[i]);
}
for(i=0; i<counter+1; i++){
for(j=0; j<4;j++) printf("%d,%d = %s\n",i,j,table[i][j]);
}
//**********UEBERGABE DES ARRAYS AN DEN MEALY-AUTOMATEN*******************************+
m1.read_program(table);
}
Dieses Programm ist quasi selbsterklärend. Man sieht, dass für die Kommunikation mit der Funktion yylex() ein 3-dimensionaler Array mit expliziten Dimensionsangaben benutzt wird. Dies ist die schlechteste unter allen möglichen Lösungen. Ein klein wenig eleganter wäre die Benutzung von einem Pointer mit Variablen für die Dimensionsgrössen. Noch besser wäre es, den Array grundsätzlich als 1-dimensionales Feld anzulegen, dessen Elemente über eine Formel berechnet werden. Wichtig ist hier, dass dieser Array in der Funktion yylex() zur Verfügung gestellt werden muss. Das usage-Programm greift darauf als eine externe Variable zu.
Nicht ganz so glücklich ist auch die Vermischung der C- und C++-I/O-Funktionen; dies kann zu unerwünschten Nebeneffekten führen. Da yylex() auf die C-Funktionen angewiessen ist, hätte dies zur Konsequenz, dass man auf die Verwendung der C++-I/O-Funktionen ganz verzichtet; dies ist in manchen Kontexten nicht sehr erstrebenswert.
Es folgt jetzt die flex-Regeldatei. Man erkennt dort sowohl die globalen Variablen, die mit der Usage-Datei geteilt werden, als auch die Aktionen, durch die yylex() dann entscheiden kann, ob es sich um einen Endzustand oder einen normalen Zustand handelt. Entsprechend werden die Daten in zwei unterschiedliche Arrays einsortiert. yylex() schaltet sich selbst ab, sobald es in der Datei das Endezeichen '#' erkennt.
/***********************+
*
* progread.l
*
*************************/
%{
#include <stdio.h>
#include <string.h>
#include "progread.h"
#define MAXTOKEN 10
%}
const int dim1 = 20;
const int dim2 = 4;
const int dim3 = 20;
char ltoken[MAXTOKEN];
char table[dim1][dim2][dim3];
int endstates[dim1];
int i=0;
int j=0;
int counter =0;
int counter2 = 0;
int flag=0;
LF \n
NOT [ \t]
LGK \{
RGK \}
LSK <
RSK >
STATE [0-9]+
SEPARATOR ,
TOKEN [a-z]+
EMPTY [_]
END #
%%
{NOT} ;
{LF} { printf("LF \n"); }
{LGK} { printf("LGK \n"); i++; flag=1;}
{RGK} { printf("RGK \n"); counter2=i; i=0; flag=0;}
{LSK} { printf("LSK \n"); i++; }
{RSK} { printf("RSK \n"); j=0; }
{STATE} { if( flag == 1) {printf("ENDSTATE\n"); endstates[i]=atoi(yytext); printf("%d\n",endstates[i]);} else {printf("STATE \n"); strcpy(table[i][j],yytext); printf("%s\n",table[i][j]);} }
{SEPARATOR} { printf("SEPARATOR \n"); j++; }
{TOKEN} { printf("TOKEN \n"); strcpy(table[i][j],yytext); printf("yylex: ltoken = %s \n",table[i][j]);}
{EMPTY} { printf("EMPTY \n"); }
{END} { printf("END \n"); counter = i; return (END);}
%%
/***********************+ * * progread.h * *************************/ #include <stdio.h> #define ENDSTATES 255 #define LF 254 #define LSK 253 #define RSK 252 #define STATE 251 #define TOKEN 250 #define SEPARATOR 248 #define END 247 #define EMPTY 247
Als nächstes folgt die Klassendatei für den Mealy-Automat und seine --noch unvollständige-- Implementierung.
Klasse Mealy-Automat
//********************************+
//
// mealy.h
//
//**************************************
#ifndef MEALY_H
#define MEALY_H
#include <string>
#include <vector>
using namespace std;
class mealy
{
/** Public methods: */
public:
/**
*
* Konstruktor
*
**/
mealy();
/**
*
* @param file_name
* Referenz auf einen Dateinamen
*/
bool read_program(char table[][4][20] );
/**
* Liest vom Input-Buffer das nächste Token.
* @param input_buffer
* Referenz auf einen Buffer vom Typ string, der eine Folge von Token enthält
*/
string read_input_token( string& input_buffer );
/** Private methods: */
private:
/**
* Sucht zu einem aktuellen Input den passenden Zustand
*/
bool do_action( );
/**
* Zeigt das Token an, das aktuell geschrieben werden soll
*/
string show_output( );
/**Attributes: */
private:
/**
* Enthält den Input fuer den Mealy-Automat
*/
string input_buffer;
/**
* Enthält den Output fuer den Mealy-Automat
*/
string output_buffer;
/**
* Enthält die Nummer des aktuellen Zustands
*/
int program_counter;
/**
* Enthält die Liste aller Endzustände, als Array
*/
vector<int> final_states;
/**
* Enthält die Liste aller aktuellen Zustaende, jeder Zustand als Teilstring
*/
vector<string> mealy_program;
};
#endif // MEALY_H
Die Implementierung ist nur soweit gezeigt, um zu sehen, wie der Mealy-Automat den Array mit den Programmdaten übernimmt.
//********************************++
//
// mealy.cpp
//
//***************************************
#include "mealy.h"
#include <string>
#include <iostream>
#include <stdio.h>
#include "progread.h"
#include <errno.h>
mealy::mealy()
{
}
bool mealy::read_program(char table[][4][20] )
{ //Liest table von mealy_usage
const int dim1=20;
const int dim2=4;
int x,y;
cout << "------------------------------program_read()-------------------------------------------"<< endl;
for( x=0; x<dim1; x++){
for( y=0; y <dim2; y++) {
cout << x << "," << y << " ADR = " << &(table[x][y])<< " = " << table[x][y] << endl;
}//End of y-loop
}//End of x-loop
}
string mealy::read_input_token( string& input_buffer )
{
}
bool mealy::do_action( )
{
}
string mealy::show_output( )
{
}
Eine einfache Mealy-Programmdatei ist die folgende mit Namen test2.mealy:
{3}
<1,a,i,1>
<1,b,_,2>
<2,b,ii,2>
<2,c,_,3>
<3,d,_,3>
#
Hier die Kompilierung und ein partieller Test:
gerd@kant:~/public_html/fh/I-PROGR3/I-PROGR3-TH/VL9> flex progread.l gerd@kant:~/public_html/fh/I-PROGR3/I-PROGR3-TH/VL9> g++ -o usage2b usage2.cpp mealy.cpp lex.yy.c -lfl gerd@kant:~/public_html/fh/I-PROGR3/I-PROGR3-TH/VL9> ./usage2b WELCHE MEALY-PROGRAMMDATEI SOLL GELADEN WERDEN (ohne Suffix .mealy) ? test2 DATEINAME : test2.mealy yylex() beginnt LGK ENDSTATE 3 RGK LF LSK STATE 1 SEPARATOR TOKEN yylex: ltoken = a SEPARATOR TOKEN yylex: ltoken = i SEPARATOR STATE 1 RSK LF LSK STATE 1 SEPARATOR TOKEN yylex: ltoken = b SEPARATOR EMPTY SEPARATOR STATE 2 RSK LF LSK STATE 2 SEPARATOR TOKEN yylex: ltoken = b SEPARATOR TOKEN yylex: ltoken = ii SEPARATOR STATE 2 RSK LF LSK STATE 2 SEPARATOR TOKEN yylex: ltoken = c SEPARATOR EMPTY SEPARATOR STATE 3 RSK LF LSK STATE 3 SEPARATOR TOKEN yylex: ltoken = d SEPARATOR EMPTY SEPARATOR STATE 3 RSK LF END KONTROLLAUSDRUCK MEALY-PROGRAMM -------------------------------------------- 0 = 0 1 = 3 0,0 = 0,1 = 0,2 = 0,3 = 1,0 = 1 1,1 = a 1,2 = i 1,3 = 1 2,0 = 1 2,1 = b 2,2 = 2,3 = 2 3,0 = 2 3,1 = b 3,2 = ii 3,3 = 2 4,0 = 2 4,1 = c 4,2 = 4,3 = 3 5,0 = 3 5,1 = d 5,2 = 5,3 = 3 ------------------------------program_read()------------------------------------------- 0,0 ADR = 0x804d640 = 0,1 ADR = 0x804d654 = 0,2 ADR = 0x804d668 = 0,3 ADR = 0x804d67c = 1,0 ADR = 0x804d690 = 1 1,1 ADR = 0x804d6a4 = a 1,2 ADR = 0x804d6b8 = i 1,3 ADR = 0x804d6cc = 1 2,0 ADR = 0x804d6e0 = 1 2,1 ADR = 0x804d6f4 = b 2,2 ADR = 0x804d708 = 2,3 ADR = 0x804d71c = 2 3,0 ADR = 0x804d730 = 2 3,1 ADR = 0x804d744 = b 3,2 ADR = 0x804d758 = ii 3,3 ADR = 0x804d76c = 2 4,0 ADR = 0x804d780 = 2 4,1 ADR = 0x804d794 = c 4,2 ADR = 0x804d7a8 = 4,3 ADR = 0x804d7bc = 3 5,0 ADR = 0x804d7d0 = 3 5,1 ADR = 0x804d7e4 = d 5,2 ADR = 0x804d7f8 = 5,3 ADR = 0x804d80c = 3 6,0 ADR = 0x804d820 = 6,1 ADR = 0x804d834 = 6,2 ADR = 0x804d848 = 6,3 ADR = 0x804d85c = 7,0 ADR = 0x804d870 = 7,1 ADR = 0x804d884 = 7,2 ADR = 0x804d898 = 7,3 ADR = 0x804d8ac = 8,0 ADR = 0x804d8c0 = 8,1 ADR = 0x804d8d4 = 8,2 ADR = 0x804d8e8 = 8,3 ADR = 0x804d8fc = 9,0 ADR = 0x804d910 = 9,1 ADR = 0x804d924 = 9,2 ADR = 0x804d938 = 9,3 ADR = 0x804d94c = 10,0 ADR = 0x804d960 = 10,1 ADR = 0x804d974 = 10,2 ADR = 0x804d988 = 10,3 ADR = 0x804d99c = 11,0 ADR = 0x804d9b0 = 11,1 ADR = 0x804d9c4 = 11,2 ADR = 0x804d9d8 = 11,3 ADR = 0x804d9ec = 12,0 ADR = 0x804da00 = 12,1 ADR = 0x804da14 = 12,2 ADR = 0x804da28 = 12,3 ADR = 0x804da3c = 13,0 ADR = 0x804da50 = 13,1 ADR = 0x804da64 = 13,2 ADR = 0x804da78 = 13,3 ADR = 0x804da8c = 14,0 ADR = 0x804daa0 = 14,1 ADR = 0x804dab4 = 14,2 ADR = 0x804dac8 = 14,3 ADR = 0x804dadc = 15,0 ADR = 0x804daf0 = 15,1 ADR = 0x804db04 = 15,2 ADR = 0x804db18 = 15,3 ADR = 0x804db2c = 16,0 ADR = 0x804db40 = 16,1 ADR = 0x804db54 = 16,2 ADR = 0x804db68 = 16,3 ADR = 0x804db7c = 17,0 ADR = 0x804db90 = 17,1 ADR = 0x804dba4 = 17,2 ADR = 0x804dbb8 = 17,3 ADR = 0x804dbcc = 18,0 ADR = 0x804dbe0 = 18,1 ADR = 0x804dbf4 = 18,2 ADR = 0x804dc08 = 18,3 ADR = 0x804dc1c = 19,0 ADR = 0x804dc30 = 19,1 ADR = 0x804dc44 = 19,2 ADR = 0x804dc58 = 19,3 ADR = 0x804dc6c = gerd@kant:~/public_html/fh/I-PROGR3/I-PROGR3-TH/VL9> l
Da in dieser Implementierungsvariante auf yylex() verzichtet wird, stehen uneingeschränkt alle C++-Sprachmittel zur Verfügung. Neben den STL-Strukturen 'string' und 'vektor', die Verwendung finden werden, ist es vor allem die map-Struktur, die für den vorliegenden Zweck günstige Eigenschaften aufweist.
Hinter der map-Struktur verbirgt sich ein balanzierter binärer Such-Baum vom Typ Red-Black-Tree. Aus Sicht des Benutzers bedeutet dies, dass die Werte im Baum anhand eines Schlüssels sowohl eingetragen als auch wieder gefunden werden können. Die Suchzeiten sind aufgrund der internen Struktur annähernd konstant. Der Schlüssel kann durch beliebige Pattern gebildet werden, die sich sortieren lassen.
Im vorliegenden Beispiel bietet es sich an, einen einzelnen Zustand des Mealy Programms als einen Knoten im Baum zu speichern und zwar so, dass der aktuelle Zustand und das aktuell gelesene Zeichen den Schlüssel ('key') bilden und das zu schreibende Zeichen mit dem Folgezustand den Wert ('value').
Ein Mealy-Zustand als Key-Value Paar
Anhand der aktuellen Eingabe und dem aktuellen Zutandszähler kann man dann jeweils einen Schlüssel generieren, der zum passenden Knoten in der map führt.
Mit dieser Datenstruktur wird die Struktur des Mealy-Automaten sehr transparent.
Mealy-Klasse
Die Schnittstelle umfasst nur noch zwei Befehle: bool read_program( string) und string read_input_token(string). Mit dem ersten Befehl wird ein Mealy-Programm geladen und mit dem zweiten Befehl kann man dem Mealy-Automat aktuellen Input übergeben. Intern wir der aktuelle Zustand verwaltet ('string program_counter') und die Menge der Endzustände ('vector
//********************************+
//
// mealy2.hpp
//
// author: g.doeben-henisch
//
//**************************************
#ifndef MEALY_HPP
#define MEALY_HPP
#include <string>
#include <vector>
#include <map>
using namespace std;
class mealy
{
/** Public methods: */
public:
/**
*
* Konstruktor
*
**/
mealy();
/**
*
* @param file_name
* Referenz auf einen Dateinamen; laedt Mealy-Programm direkt
*/
bool read_program( string);
/**
* Liest vom Input-Buffer das nächste Token.
* @param input_buffer
* Referenz auf einen Buffer vom Typ string, der eine Folge von Token enthält
* Gibt Antwort als String zurueck
*/
string read_input_token( string& input_mealy );
/**Attributes: */
private:
/**
* Enthält die Nummer des aktuellen Zustands
*/
string program_counter;
/**
* Enthält die Liste aller Endzustände, als Array
*/
vector<string> final_states;
/**
* Enthält das Mealyprogramm als STL-map
*/
typedef map<string,string> MPSS;
MPSS mealy_program;
/**
* Enthält die unverarbeitete Programm-Datei
*/
string input_buffer;
};
#endif // MEALY_HPP
Die eigentliche Arbeit wird dann in der Implementierungsdatei 'mealy2.cpp' beschrieben. Die Grundidee besteht darin, dass der Automat zuerst ein Programm lädt, dieses in eine map-Struktur konvertiert und dann aktuellen Input mit dem aktuellen Zustandszähler als Schlüssel benutzt, um die vorher definierte Aktion aus der map auszulesen und auszuführen.
//******************************++
//
// mealy2.cpp
//
// author: g.doeben-henisch
//
//******************************************
#include "mealy2.hpp"
#include <cstdlib> // fuer exit()
#include <iostream>
#include <fstream>
using namespace std;
mealy::mealy( )
{
// Program-Counter wird auf Startnummer 1 festgelegt
//Alternative: '1' als Defaultwert und ansonsten flexibel bei Aufruf
program_counter+="1";
}
bool mealy::read_program( string file_name )
{
// some commonly used strings for parsing
string glk("{");
string grk("}");
string slk("<");
string srk(">");
string com(",");
string::size_type idx;
char c;
string::size_type i,hold;
int len; // lenght of a string
int begin, middle, end; // points in a substring
int fsidx; // index into final states array
string state, key, value;
// open input file
ifstream file(file_name.c_str());
// file opened?
if (! file) {
// NO, abort program
cerr << "can't open input file \"" << file_name << "\""
<< endl;
exit(EXIT_FAILURE);
}
// copy file contents to input_buffer
input_buffer="";
while (file.get(c)) {
input_buffer.push_back(c);
}
len = input_buffer.length();
cout << "MEALY : Mein Input-Buffer Inhalt ist = " << input_buffer << endl;
cout << "LAENGE DES INPUT_BUFFERS : " << len << " , " << input_buffer.length() << endl;
cout << "----------------------------------------------------- " << endl;
// SEARCHING FOR THE END-STATES BY CURLY BRACES
// Finding the positions of the curly braces
idx = input_buffer.find(glk,0);
if(idx == string::npos ) { cerr << " DER TEILSTRING " << glk << " kommt nicht vor! " << endl;
exit(EXIT_FAILURE); }
else {cout << glk << " KOMMT VOR AN POS: " << idx << endl;
}
begin = idx;
idx = input_buffer.find(grk,idx+1);
if(idx == string::npos ) { cerr << " DER TEILSTRING " << grk << " kommt nicht vor! " << endl;
exit(EXIT_FAILURE); }
else {cout << grk << " KOMMT VOR AN POS: " << idx << endl;
}
end = idx;
cout << "BEGINN " << begin << " END " << end << endl;
// finding the substrings for individual end states
// case in which there is only one final state
fsidx = 0;
idx = input_buffer.find(com,begin+1);
if(idx > end ) { //Only one final state
final_states.push_back( input_buffer.substr(begin+1,end-(begin+1)));
cout << " FS : (" << begin+1 << ", " << end-1 << ") " << final_states[fsidx] << endl;
}
// There is more than one final state
else {
cout << "MORE THAN ONE FS " << endl;
middle = idx;
do {
// building substring for final state
final_states.push_back( input_buffer.substr(begin+1,middle-(begin+1)));
cout << " FS : (" << begin+1 << ", " << middle-1 << ") " << final_states[fsidx] << endl;
begin=idx+1;
fsidx++;
idx = input_buffer.find(com,begin);
} while(idx < end);
// Register the last final state
final_states.push_back ( input_buffer.substr(begin,end-begin ) );
cout << " FS : (" << begin << ", " << end-1 << ") " << final_states[fsidx] << endl;
}//End-of-else
cout << "----------------------------------------------------- " << endl;
// SEARCHING FOR THE ORDINARY STATES BY ANGLE BRACKETS AND COMMAS
i=end+1;
while(i < len-2){
idx = input_buffer.find(slk,i+1);
if(idx == string::npos ) { cerr << " DER TEILSTRING " << slk << " kommt nicht vor! " << endl;
exit(EXIT_FAILURE); }
else {cout << slk << " KOMMT VOR AN POS: " << idx << endl;
}
begin = i= idx;
idx = input_buffer.find(srk,i+1);
if(idx == string::npos ) { cerr << " DER TEILSTRING " << srk << " kommt nicht vor! " << endl;
exit(EXIT_FAILURE); }
else {cout << srk << " KOMMT VOR AN POS: " << idx << endl;
}
end = i = idx;
cout << "BEGINN = " << begin << endl;
cout << "ENDE = " << end << endl;
state = input_buffer.substr(begin,end+1-begin); //From begin (end+1-begin)-times many chars
cout << " <TEILSTRING> : " << state << endl;
// finding the substrings for key and value
// looking for the second comma dividing the state into key and value
i=begin;
idx = input_buffer.find(com,i+1);
if(idx == string::npos ) { cerr << " DER TEILSTRING " << com << " kommt nicht vor! " << endl;
exit(EXIT_FAILURE); }
else {cout << com << " KOMMT VOR AN POS: " << idx << endl;
}
i=idx;
idx = input_buffer.find(com,i+1);
if(idx == string::npos ) { cerr << " DER TEILSTRING " << com << " kommt nicht vor! " << endl;
exit(EXIT_FAILURE); }
else {cout << com << " KOMMT VOR AN POS: " << idx << endl;
}
// building substrings key and value
middle =i = idx;
key = input_buffer.substr(begin+1,middle-(begin+1));
cout << " KEY : (" << begin+1 << ", " << middle-1 << ") " << key << endl;
value = input_buffer.substr(middle+1,end-(middle));
cout << " VALUE : (" << middle+1 << ", " << end << ") " << value << endl;
// inserting the key and value into the map
mealy_program.insert(make_pair(key,value));
i=end;
}//End-of-while i
// show all elements of the map
cout << "MEALY : Mein MAP- Inhalt ist = " << endl;
cout << "----------------------------------------------------- " << endl;
MPSS::iterator pos;
for(pos = mealy_program.begin(); pos != mealy_program.end(); ++pos){
cout << "MAP SCHLUESSEL : " << pos->first << " , MAP WERT : " << pos->second << endl;
}
cout << "----------------------------------------------------- " << endl;
}
string mealy::read_input_token( string & input_mealy )
{
// some commonly used strings for parsing
string glk("{");
string grk("}");
string slk("<");
string srk(">");
string com(",");
string key_generate, value_received;
string token_to_write, next_state;
int i, begin, middle, end;
string::size_type idx;
cout << "MEALY : Mein Input ist = " << input_mealy << endl;
// built key by concatenating input with comma and program_counter
key_generate = program_counter + "," + input_mealy;
// asking the value from the map by giving the key
value_received = mealy_program[key_generate];
cout << "VALUE RECEIVED : " << value_received << " LAENGE = " << value_received.length() << endl;
// parsing the value to get the token to write and the new program state
// find the first comma which separates token_to_write from next_state
idx = value_received.find(com,0);
if(idx == string::npos ) { cerr << " DER TEILSTRING " << com << " kommt nicht vor! " << endl;
exit(EXIT_FAILURE); }
else {cout << com << " KOMMT VOR AN POS: " << idx << endl;
}
middle = idx;
token_to_write = value_received.substr(0,middle-0);
cout << "T2W : " << token_to_write << endl;
// find the the next right angle bracket which terminates the next state
idx = value_received.find(srk,middle+1);
if(idx == string::npos ) { cerr << " DER TEILSTRING " << srk << " kommt nicht vor! " << endl;
exit(EXIT_FAILURE); }
else {cout << srk << " KOMMT VOR AN POS: " << idx << endl;
}
next_state = value_received.substr(middle+1,idx-1-middle);
cout << "NxtSTATE : " << next_state << endl;
// test whether the next state is a final state
end = final_states.size();
for(i = 0; i < end ; i++) {
cout << i << " = " << final_states[i] << endl;
if ( final_states[i] == next_state ){ token_to_write = "ENDSTATE"; break;}
}
return( token_to_write);
}
Die Steuerung des Automaten erfolgt dann wie gewohnt von dem Usage-Programm aus: über das Usage-Programm kann der Benutzer ein Mealy-Programm auswählen, dessen Namen dann dem Mealy-Automat übergeben wird. Hat der Mealy-Automat das Programm geladen, dann kann der Benutzer beliebigen Input --im Sinne des zuvor geladenen Programms-- eingeben und der Mealy-Automat reagiert auf der Basis des gerade geladenen Programms.
//******************************++
//
// mealy_usage2.cpp
//
// author: g.doeben-henisch
//
//******************************************
#include "mealy2.hpp"
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
int main(){
char next, next2; // Schleifenvariablen für Programmablauf
string file_name, tmp_name, input_mealy;
const string suffix ("mealy");
next = 'y'; // Aeussere Schleife zum Laden eines Mealy-Programms
mealy m1; // Instantiierung eines Mealy-Automaten
// BEGINN AUSSENSCHLEIFE:
while(next == 'y' ){
// BENUTZER SOLL DATEINAMEN FUER MEALY-PROGRAMMDATEI EINGEBEN
tmp_name="";
file_name="";
cout << "WELCHE MEALY-PROGRAMMDATEI SOLL GELADEN WERDEN (ohne Suffix .mealy) ? " << endl;
cin >> tmp_name;
file_name = tmp_name + '.' + suffix;
cout << "DATEINAME : " << file_name << endl;
// PROGRAMM-DATEI OEFFNEN UND EINLESEN
m1.read_program( file_name);
next2='y';
// BEGINN INNEN-SCHLEIFE ZUR ABARBEITUNG DES PROGRAMMS
while(next2 == 'y' ){
// INPUT FUER MEALY-AUTOMAT
// BEARBEITUNG DURCH MEALY-PROGRAMM
// OUTPUT SCHREIBEN
cout << "IHRE EINGABE BITTE : " << endl;
cin >> input_mealy;
cout << "Antwort von Mealy = " << m1.read_input_token(input_mealy ) << endl;
cout << "MOECHTEN SIE NOCH EINE EINGABE MACHEN (y/n) ? " << endl;
cin >> next2;
}//End-of while innere Schleife
// PROGRAMM ENDE bzw. NEUES MEALY-PROGRAMM
cout << "MOECHTEN SIE NOCH EIN MEALYPROGRAMM LADEN (y/n) ? " << endl;
cin >> next;
}//End-of-while next
exit(1);
}
Für die Kompilierung wird ein einfaches Makefile benutzt, das dan Namen hat 'Makefile.mealy':
############################################################################# # Makefile for building: mealy_sim ############################################################################# ####### Compiler, tools and options CC = gcc CXX = g++ CFLAGS = -pipe -O2 -march=i586 -mcpu=i686 -fmessage-length=0 -fPIC -DNO_DEBUG -Wall -W -g CXXFLAGS = -pipe -O2 -march=i586 -mcpu=i686 -fmessage-length=0 -fPIC -DNO_DEBUG -Wall -W -g LIBS = ####### Files HEADERS = mealy2.hpp OBJECTS = mealy_usage2.o mealy2.o TARGET = mealy_sim ############## RULES FOR GENERATION $(TARGET): $(OBJECTS) g++ -o $(TARGET) $(OBJECTS) $(LIBS) mealy_usage2.o: mealy_usage2.cpp mealy2.hpp g++ -c mealy_usage2.cpp mealy2.o: mealy2.cpp mealy2.hpp g++ -c mealy2.cpp clean: rm $(TARGET) $(OBJECTS)
Der Aufruf dieses Makefiles geschieht wie folgt:
gerd@kant:~/public_html/fh/I-PROGR3/I-PROGR3-TH/VL9/MEALY-MAP> make -f Makefile.mealy g++ -c mealy_usage2.cpp g++ -c mealy2.cpp g++ -o mealy_sim mealy_usage2.o mealy2.o
Im ersten Beispiel wird ein mealy-programm gladen, das nur einen Endzustand hat. Es heisst 'test1.mealy'.
gerd@kant:~/public_html/fh/I-PROGR3/I-PROGR3-TH/VL9/MEALY-MAP> ./mealy_sim
WELCHE MEALY-PROGRAMMDATEI SOLL GELADEN WERDEN (ohne Suffix .mealy) ?
test1
DATEINAME : test1.mealy
MEALY : Mein Input-Buffer Inhalt ist = {2}
<1,0,0,1>
<1,1,i,1>
<1,2,ii,1>
<1,3,iii,1>
<1,4,iv,1>
<1,5,v,1>
<1,6,vi,1>
<1,7,vii,1>
<1,8,viii,1>
<1,9,ix,1>
<1,_,_,2>
LAENGE DES INPUT_BUFFERS : 125 , 125
-----------------------------------------------------
{ KOMMT VOR AN POS: 0
} KOMMT VOR AN POS: 2
BEGINN 0 END 2
FS : (1, 1) 2
-----------------------------------------------------
< KOMMT VOR AN POS: 4
> KOMMT VOR AN POS: 12
BEGINN = 4
ENDE = 12
: <1,0,0,1>
, KOMMT VOR AN POS: 6
, KOMMT VOR AN POS: 8
KEY : (5, 7) 1,0
VALUE : (9, 12) 0,1>
< KOMMT VOR AN POS: 14
> KOMMT VOR AN POS: 22
BEGINN = 14
ENDE = 22
: <1,1,i,1>
, KOMMT VOR AN POS: 16
, KOMMT VOR AN POS: 18
KEY : (15, 17) 1,1
VALUE : (19, 22) i,1>
< KOMMT VOR AN POS: 24
> KOMMT VOR AN POS: 33
BEGINN = 24
ENDE = 33
: <1,2,ii,1>
, KOMMT VOR AN POS: 26
, KOMMT VOR AN POS: 28
KEY : (25, 27) 1,2
VALUE : (29, 33) ii,1>
< KOMMT VOR AN POS: 35
> KOMMT VOR AN POS: 45
BEGINN = 35
ENDE = 45
: <1,3,iii,1>
, KOMMT VOR AN POS: 37
, KOMMT VOR AN POS: 39
KEY : (36, 38) 1,3
VALUE : (40, 45) iii,1>
< KOMMT VOR AN POS: 47
> KOMMT VOR AN POS: 56
BEGINN = 47
ENDE = 56
: <1,4,iv,1>
, KOMMT VOR AN POS: 49
, KOMMT VOR AN POS: 51
KEY : (48, 50) 1,4
VALUE : (52, 56) iv,1>
< KOMMT VOR AN POS: 58
> KOMMT VOR AN POS: 66
BEGINN = 58
ENDE = 66
: <1,5,v,1>
, KOMMT VOR AN POS: 60
, KOMMT VOR AN POS: 62
KEY : (59, 61) 1,5
VALUE : (63, 66) v,1>
< KOMMT VOR AN POS: 68
> KOMMT VOR AN POS: 77
BEGINN = 68
ENDE = 77
: <1,6,vi,1>
, KOMMT VOR AN POS: 70
, KOMMT VOR AN POS: 72
KEY : (69, 71) 1,6
VALUE : (73, 77) vi,1>
< KOMMT VOR AN POS: 79
> KOMMT VOR AN POS: 89
BEGINN = 79
ENDE = 89
: <1,7,vii,1>
, KOMMT VOR AN POS: 81
, KOMMT VOR AN POS: 83
KEY : (80, 82) 1,7
VALUE : (84, 89) vii,1>
< KOMMT VOR AN POS: 91
> KOMMT VOR AN POS: 102
BEGINN = 91
ENDE = 102
: <1,8,viii,1>
, KOMMT VOR AN POS: 93
, KOMMT VOR AN POS: 95
KEY : (92, 94) 1,8
VALUE : (96, 102) viii,1>
< KOMMT VOR AN POS: 104
> KOMMT VOR AN POS: 113
BEGINN = 104
ENDE = 113
: <1,9,ix,1>
, KOMMT VOR AN POS: 106
, KOMMT VOR AN POS: 108
KEY : (105, 107) 1,9
VALUE : (109, 113) ix,1>
< KOMMT VOR AN POS: 115
> KOMMT VOR AN POS: 123
BEGINN = 115
ENDE = 123
: <1,_,_,2>
, KOMMT VOR AN POS: 117
, KOMMT VOR AN POS: 119
KEY : (116, 118) 1,_
VALUE : (120, 123) _,2>
MEALY : Mein MAP- Inhalt ist =
-----------------------------------------------------
MAP SCHLUESSEL : 1,0 , MAP WERT : 0,1>
MAP SCHLUESSEL : 1,1 , MAP WERT : i,1>
MAP SCHLUESSEL : 1,2 , MAP WERT : ii,1>
MAP SCHLUESSEL : 1,3 , MAP WERT : iii,1>
MAP SCHLUESSEL : 1,4 , MAP WERT : iv,1>
MAP SCHLUESSEL : 1,5 , MAP WERT : v,1>
MAP SCHLUESSEL : 1,6 , MAP WERT : vi,1>
MAP SCHLUESSEL : 1,7 , MAP WERT : vii,1>
MAP SCHLUESSEL : 1,8 , MAP WERT : viii,1>
MAP SCHLUESSEL : 1,9 , MAP WERT : ix,1>
MAP SCHLUESSEL : 1,_ , MAP WERT : _,2>
-----------------------------------------------------
IHRE EINGABE BITTE :
3
MEALY : Mein Input ist = 3
VALUE RECEIVED : iii,1> LAENGE = 6
, KOMMT VOR AN POS: 3
T2W : iii
> KOMMT VOR AN POS: 5
NxtSTATE : 1
0 = 2
Antwort von Mealy = iii
MOECHTEN SIE NOCH EINE EINGABE MACHEN (y/n) ?
y
IHRE EINGABE BITTE :
6
MEALY : Mein Input ist = 6
VALUE RECEIVED : vi,1> LAENGE = 5
, KOMMT VOR AN POS: 2
T2W : vi
> KOMMT VOR AN POS: 4
NxtSTATE : 1
0 = 2
Antwort von Mealy = vi
MOECHTEN SIE NOCH EINE EINGABE MACHEN (y/n) ?
y
IHRE EINGABE BITTE :
9
MEALY : Mein Input ist = 9
VALUE RECEIVED : ix,1> LAENGE = 5
, KOMMT VOR AN POS: 2
T2W : ix
> KOMMT VOR AN POS: 4
NxtSTATE : 1
0 = 2
Antwort von Mealy = ix
MOECHTEN SIE NOCH EINE EINGABE MACHEN (y/n) ?
y
IHRE EINGABE BITTE :
_
MEALY : Mein Input ist = _
VALUE RECEIVED : _,2> LAENGE = 4
, KOMMT VOR AN POS: 1
T2W : _
> KOMMT VOR AN POS: 3
NxtSTATE : 2
0 = 2
Antwort von Mealy = ENDSTATE
MOECHTEN SIE NOCH EINE EINGABE MACHEN (y/n) ?
n
Ein Beispiel mit mehr als einem Endzustand. Die Programmdatei heisst 'test2.mealy'.
MOECHTEN SIE NOCH EIN MEALYPROGRAMM LADEN (y/n) ?
y
WELCHE MEALY-PROGRAMMDATEI SOLL GELADEN WERDEN (ohne Suffix .mealy) ?
test2
DATEINAME : test2.mealy
MEALY : Mein Input-Buffer Inhalt ist = {2,3}
<1,a,i,1>
<1,b,ii,2>
<1,c,iii,3>
LAENGE DES INPUT_BUFFERS : 39 , 39
-----------------------------------------------------
{ KOMMT VOR AN POS: 0
} KOMMT VOR AN POS: 4
BEGINN 0 END 4
MORE THAN ONE FS
FS : (1, 1) 2
FS : (3, 3) 3
-----------------------------------------------------
< KOMMT VOR AN POS: 6
> KOMMT VOR AN POS: 14
BEGINN = 6
ENDE = 14
: <1,a,i,1>
, KOMMT VOR AN POS: 8
, KOMMT VOR AN POS: 10
KEY : (7, 9) 1,a
VALUE : (11, 14) i,1>
< KOMMT VOR AN POS: 16
> KOMMT VOR AN POS: 25
BEGINN = 16
ENDE = 25
: <1,b,ii,2>
, KOMMT VOR AN POS: 18
, KOMMT VOR AN POS: 20
KEY : (17, 19) 1,b
VALUE : (21, 25) ii,2>
< KOMMT VOR AN POS: 27
> KOMMT VOR AN POS: 37
BEGINN = 27
ENDE = 37
: <1,c,iii,3>
, KOMMT VOR AN POS: 29
, KOMMT VOR AN POS: 31
KEY : (28, 30) 1,c
VALUE : (32, 37) iii,3>
MEALY : Mein MAP- Inhalt ist =
-----------------------------------------------------
MAP SCHLUESSEL : 1,a , MAP WERT : i,1>
MAP SCHLUESSEL : 1,b , MAP WERT : ii,2>
MAP SCHLUESSEL : 1,c , MAP WERT : iii,3>
-----------------------------------------------------
IHRE EINGABE BITTE :
a
MEALY : Mein Input ist = a
VALUE RECEIVED : i,1> LAENGE = 4
, KOMMT VOR AN POS: 1
T2W : i
> KOMMT VOR AN POS: 3
NxtSTATE : 1
0 = 2
1 = 3
2 = 2
3 = 3
Antwort von Mealy = i
MOECHTEN SIE NOCH EINE EINGABE MACHEN (y/n) ?
y
IHRE EINGABE BITTE :
b
MEALY : Mein Input ist = b
VALUE RECEIVED : ii,2> LAENGE = 5
, KOMMT VOR AN POS: 2
T2W : ii
> KOMMT VOR AN POS: 4
NxtSTATE : 2
0 = 2
Antwort von Mealy = ENDSTATE
MOECHTEN SIE NOCH EINE EINGABE MACHEN (y/n) ?
y
IHRE EINGABE BITTE :
c
MEALY : Mein Input ist = c
VALUE RECEIVED : iii,3> LAENGE = 6
, KOMMT VOR AN POS: 3
T2W : iii
> KOMMT VOR AN POS: 5
NxtSTATE : 3
0 = 2
1 = 3
Antwort von Mealy = ENDSTATE
MOECHTEN SIE NOCH EINE EINGABE MACHEN (y/n) ?
n
MOECHTEN SIE NOCH EIN MEALYPROGRAMM LADEN (y/n) ?
n
gerd@kant:~/public_html/fh/I-PROGR3/I-PROGR3-TH/VL9/MEALY-MAP>
Aufgrund der fortgeschrittenen Zeit ist es nun nicht mehr möglich, dieser Frage im Rahmen der Vorlesung ausführlich nachzugehen. Es ist jedem überlassen, hier auf eigene Faust Nachforschungen anzustellen. Die möglichen Erkenntnisse sind sicherlich wertvoll, erschliessen sie doch einen tieferen Zusammenhang zwischen den Elementen einer endlichen Maschine wie dem Mealy-Automaten und der zu lösenden Aufgabe.
Selbst diese Frage wird aufgrund der Zeitknappheit nicht beantwortet werden. Prinzipiell ist nur klar, dass die Klasse 'mealy' als Datentyp natürlich in der Klasse 'automatic_player' zur Verfügung steht. Man könnte also innerhalb der Klasse 'automatic_player' diverse Mealy-Automaten als Objekte benutzen, so, wie man 'string', 'vector' oder 'map' benutzen kann!
Wenigstens kurz soll noch das Konzept der Turingmaschine angesprochen werden. Eine Beschreibung der Turingmaschine mit Beispielen und interessanten Links findet sich hier.
Aufschlussreich ist ein direkter Vergleich von Mealy-Automat und Turingmaschine. Grundsätzlich ist klar, dass ein Mealy-Automat eine abgeschwächte Form der Turingmaschine darstellen kann (Begründung in der theoretischen Informatik). Interessant ist allerdings die Frage, was macht aus einem Mealy-Automaten eine Turingmaschine? Während ein Mealy-Automat sehr beschränkt ist, kann eine Turingmaschine alles, was unter den Begriff der Berechenbarkeit fällt, und dies ist --bedenkt man, dass das Gehirn möglicherweise auch eine Ausprägung einer Turingmaschine ist nicht gerade wenig. Was alles unterscheidet eine Turingmaschine von einem Mealy-Automaten?
Vergleich Mealy-Automat zu Turingmaschine
Der direkte Vergleich offenbart, dass der Unterschied auf den ersten Blick sehr geringfügig ist. Im wesentlichen sind es nur drei Eigenschaften: (i) während das Input-Band und das Outputband beim Mealy-Automaten getrennt sind, ist es bei der Turingmaschine integriert; (ii) während die Lese- und Schreibköpfe beim Mealy-Automaten nur in eine Richtung bewegt werden können, können sie bei der Turingmaschine in beide Richtungen bewegt werden; (iii) damit die Lese-Schreib-Operationen möglich werden, müssen die Zustände der Turingmaschine ein zusätzliches Element enthalten, in dem gesagt wird, welche Bewegungen der Lese-Schreibkopf ausführen soll. Das ist alles.
Dies ist verblüffend, denn der Kern der Turingmaschine ist weiterhin ein endlicher deterministischer Automat! Offensichtlich ist das, was die Stärke der Turingmaschine ausmacht die neue Fähigkeit, die 'Vergangenheit' 'wiederholen' zu können und --über den Umweg des Bandes-- eigene Zustände schreiben und lesen zu können. Eine Turingmaschine kann tatsächlich sich selbst und jede andere denkbare Turingmaschine simulieren; dies führt zum Begriff der universellen Turingmaschine.
Auf diese und weitere Aspekte der Turingmaschine kann hier aber nicht eingegangen werden.
In den Übungsstunden