Prof. Franz Schweiggert Abteilung Angewandte Informationsverarbeitung 5. November 2002
Christian Ehrhardt Blatt 2


Uni Logo



Allgemeine Informatik (WS 2002/2003)


Abgabetermin 3.9.2002

Endliche Automaten (10 Punkte)

\includegraphics{printf}

Die Aufgabe dieses Blattes ist es, ein C-Programm zu schreiben, das selbst wieder ein C-Programm von der Standardeingabe liest und darin alle Stringkonstanten daraufhin überprüft, ob sie einen korrekten Formatstring für (eine vereinfachte Version von) printf darstellen. Mit anderen Worten: Es ist ein Programm zu schreiben, das feststellt, ob die Eingabe durch den in der Abbildung dargestellten endlichen Automaten erkannt wird. Außerdem soll jedes Mal beim Zustandsübergang von A nach Start der Text ``OK'' und beim Übergang von Error nach Start der Text ``Error'' ausgegeben werden. Wenn sich der Automat am Ende der Eingabe nicht im Zustand Start befindet soll der Text ``Unterminated'' ausgegeben werden. C Syntax, die über den Automaten hinausgeht muß nicht gesondert berücksichtigt werden (z.B. ein einzelnes Anführungszeichen in einem Kommentar).
Hinweis: Die switch-Anweisung kann recht hilfreich sein, um endliche Automaten zu implementieren.

Wiederholung: Endliche Automaten

Ein endlicher Automat besteht aus verschiedenen Zuständen und einer Übergangfunktion. Zu Beginn befindet sich der Automat im Zustand Start und bei jedem gelesenen Zeichen findet ein Zustandsübergang zu einem neuen Zustand statt. Der neue Zustand hängt dabei nur vom alten Zustand und vom gelesenen Zeichen ab.
In der oben gezeigten Grafik sind die Kreise die Zustände und die Zustandsübergänge werden durch Pfeile beschrieben. Wenn sich der Automat z.B. in Zustand Esc befindet und das Zeichen ``a'' gelesen wurde, findet ein Zustandsübergang zu Zustand A statt. Wäre dagegen das Zeichen ``x'' gelesen worden, so würde ein Zustandsübergang zu Error stattfinden.

Testfälle

Um zu überprüfen, ob das Programm korrekt arbeitet sollte es zunächst mit sich selbst als Eingabe getestet werden. Die Ausgabe muß dabei nicht zwangsläufig nur aus ``OK''s bestehen, aber falls das nicht der Fall ist solltet Ihr erklären können, warum der Automat mit eurem Programm nicht richtig umgehen kann. Eine Datei mit weiteren Testfällen gibt es bei den Ergänzungen zu diesem Blatt.



Christian Ehrhardt 2002-11-05