|
I-PROGR3 WS03 - PROGRAMMIEREN3 - Übungsaufgabe Nr.8Achtung : für diese Übungsaufgabe kann es abweichend von der allgemeinen Regel bis zu 7 Punkten geben !!! AUTHOR: Gerd Döben-Henisch DATE OF FIRST GENERATION: Sept-14, 2003 DATE OF LAST CHANGE: Dez-4, 2003 EMAIL: Gerd Döben-Henisch |
Der Kontext der heutigen Aufgabe ist wie folgt gegeben (siehe Schaubild):
Gesamtprojekt Programmieren 3
Ein menschlicher Spieler ('user') kann über eine Benutzerschnittstelle Dame spielen. Die Benutzerschnittstelle ist ein Usage-programm, das gegen Ende des Semesters mit einer graphischen Oberfläche versehen werden soll (Qt). In der Usage-Datei ist die syntaktische Analyse mittels flex und bison integriert. Dazu gibt es dann die Klasse Welt, die eine Spielumgebung in Form eines Spielbretts zur Verfügung stellt und jetzt einen automatischen Spieler ('automatic player'), der die schwarzen Steine führen soll. Das Innenleben des automatischen Spielers soll mit drei unterschiedlichen Konzepten realisiert werdeen: (i) mit einem einfachen Mealy-Automaten, (ii) mit einer Turingmaschine und (iii) mit einem Task-Graphen.
Bevor wir einen Mealy-Automaten direkt als Klasse in die Klasse autimatic_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.
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.
Ein möglicher Entwurf für das Aktivitätsdiagramm des Mealy-Simulators könnte das folgende sein:
Aktivitätsdiagramm des Simulator-Usage-Programms
Die eigentliche Aufgabe lautet dann wie folgt:
Implementieren sie in C++ einen Simulator für Mealy-Automaten, der die vorausgehende Beschreibung erfüllt. Packen Sie den Mealy-Automaten in eine Klasse 'mealy' und den Rest des Programms in ein Usage-Programm.
Erstellen Sie eine Diskette, die sich unter Linux laden und abspielen lässt.
Erstellen Sie von dem Quelltext ihres Programmes einen gedruckten Text
Diskette und Text müssen ihren Namen und ihre Matr.Nr. tragen, dazu Nr. der Übungsaufgabe.
Geben Sie Diskette und Text zu Beginn der nächsten Übung am Do, 11.Dez. ab.
Stellen Sie ihr Programm im Rahmen eines kleinen Vortrags vor.