In der technischen Informatik haben wir eine Vorstellung entwickelt, wie reale Computer funktionieren. Logische Schaltungen führten uns zu Addieren und Multiplizierern. Jetzt wollen wir viel allgemeiner klären, was ein beliebiger, also auch noch nicht gebauter Computer theoretisch maximal kann. Dazu beginnen wir aber etwas friedlicher und schauen uns zunächst übliche Automaten an.

Wir betrachten einen Getränkeautomaten. Der Automat soll zwei verschiedene Getränke Cola und Fanta zum Preis von 2,00 € ausgeben. Der Automat akzeptiert 50-Cent-, 1-€- und 2€-Stücke. Der Automat soll einen Geldrückgabeknopf besitzen, damit man Geld zurück erhält zurück, wenn man es sich anders überlegt hat. Überzahltes Geld wirft der Automat automatisch aus. Dieser Automat lässt sich in einem Zustandsdiagramm sehr gut darstellen. Die Kreise stehen dabei für die Zustände, die hier 0, 05, 1, 15 und 2 weisen. Dabei ist 0 der Startzustand des Automaten

Die Pfeile beschreiben die Übergänge zwischen den einzelnen Zuständen in Abhängigkeit von der getätigten Eingabe (auf den Pfeilen vor dem Schrägstrich. Die möglichen Eingaben sind 0,5 €, 1 €, 2 €, C für Cola gewünscht , F für Fanta gewünscht und R für Geldrückgabe. Damit der Automat nicht in einen undefinierten Zustand gerät, muss er für alle 5 Zustände auf jede Eingabe reagieren können, d.h. es müssen von jedem Zustand 6 Pfeile ausgehen. Zu jedem Übergang gehört auch eine Ausgabe (hinter dem Schrägstrich). Unser Automat hat keine Endzustände.

Fassen wir das noch mal allgemein zusammen

Ein endlicher Automat besteht aus

1. einer Menge von Eingaben, dem Eingabealphabet.
2. (event.) einer Menge von Ausgaben, dem Ausgabealphabet.
3. einer Menge von Zuständen
4. einem Startzustand aus der Menge der Zustände
5. (event.) ein oder mehreren Endzuständen aus der Menge der Zustände
6. einer Übergangsfunktion, die jeder Kombination Zustand-Eingabe einen Folgezustand zuordnet.
7. (event.) einer Ausgabefunktion, die jeder Kombination Zustand-Eingabe eine Ausgabe zuordnet.

Übergangsfunktion und Ausgabefunktion lassen sich statt im Zustandsdiagramm auch in Tabellenform darstellen.

Der Getränkeautomat hat als Eingaben „0,5€, 1€, 2€, Cola(C), Fanta(F), Rückgabe(R)“ und als Ausgaben „Cola kommt(Ck)“, „Fanta kommt(Fk)“, 0,5€ (zurück), 1€ (zurück), 1,5€ (zurück), 2€ (zurück), Nichts zurück (-)“.

1. Stellen Sie beim Colaautomat Übergangsfunktion und Ausgabefunktion in Tabellenform dar.
2. Ein Spielautomat (Einarmiger Bandit) hat nur die Gewinnstufe 3 €. Jedes Spiel startet durch Druck auf einen Knopf und kostet (egal ob Gewinn oder Verlust) 1 €. Der Automat akzeptiert 1 € und 2 € Stücke. Es kann jederzeit beliebig Geld eingeworfen werden, allerdings bis maximal 5 €. Überschreitet das Guthaben durch Einwurf oder Gewinn die 5 €, dann wird das überzählige Geld ausgeworfen. Es gibt einen Geldrückgabeknopf, der das komplette Guthaben auszahlt. Entwirf den oben beschriebenen Automat und erläutere gegebenenfalls deine Überlegungen. Gib konkret alle Bestandteile dieses endlichen Automaten an.
3. Ein altes Rätsel lautet: Ein Bauer, der einen Wolf, eine Ziege und einen Kohlkopf dabei hat, muss einen Fluss überqueren. Das Boot ist aber so klein, dass er nur eines der Dinge mitnehmen kann. Lässt er jedoch Wolf und Ziege auf einer Seite des Ufers allein, frisst der Wolf die Ziege. Genauso ergeht es dem Kohlkopf, wenn er mit der Ziege allein ist. Wie kann der Bauer alle Dinge unbeschadet ans andere Ufer bringen? Erstelle dazu einen endlichen Automaten mit geeigneten Zuständen. Zur Vereinfachung können alle Übergänge, die zum Verlust eines der Dinge führen und damit das Rätsel nicht lösen weggelassen werden. Welche Bestandteile muss der Automat haben, welche nicht?
4. Ein Automat verkauft Fahrkarten im Wert von 3€ und zwar nimmt er Ein- und Zwei-Eurostücke an. Sobald genügend Geld eingeworfen ist, fällt die Fahrkarte in das Entnahmefach, zu viel eingeworfenes Geld wird nicht zurückgegeben. Entwirf den beschriebenen Automat und erläutere gegebenenfalls deine Überlegungen. Gib konkret alle Bestandteile dieses endlichen Automaten an.
5. Der Automat Hund wird wie folgt charakterisiert: Eingabe: streicheln, knuffen Zustand: friedfertig, zweifelnd, wütend Ausgabe: wedeln, bellen Ist der Hund friedfertig, so folgt auf die Eingabe „streicheln“ die Ausgabe „wedeln“. Wird der friedfertige Hund geknufft, wedelt er weiter, geht aber in den Zustand zweifelnd. Wird der zweifelnde Hund gestreichelt, so wedelt er und wird friedfertig, wird er nochmals geknufft, so bellt er und wird wütend. Der wütende Hund reagiert auf knuffen mit bellen und bleibt wütend, auf streicheln bellt er weiter, wird aber friedfertig. Entwirf ein Zustandsdiagramm dieses Automaten.
6. Vier Kessel werden elektrisch beheizt, die Zuleitungen verkraften aber nur den gleichzeitigen Betrieb von zwei Kesseln. Entwickeln Sie einen endlichen Automaten und die zugehörige Schaltung, die die folgenden Signale erzeugt: W: Warten, keine weitere Heizstelle darf zugeschaltet werden. Z: Zuschalten, eine weiterer Kessel darf zugeschaltet werden. A: Alarm, mehr als zwei Kessel sind eingeschaltet.

Für die Informatik von besonderer Bedeutung sind die sogenannten Akzeptoren oder erkennenden Automaten, das sind endliche Automaten mit Anfangs und Endzuständen ohne Ausgabe. Eine Folge von Eingaben, die vom Anfangszustand zu einem der Endzustände führt, heißt akzeptiertes Wort. Alle akzeptierten Worte bilden die Sprache des Automaten.

Die Sprache des Akzeptors soll eine normale Kommazahl sein. Das Eingabealphabet besteht aus {+,-,0,1,…,9,Komma}. Ausgaben gibt es ja nicht.

Nennen Sie fünf auch von der Art verschiedene Zahlen, die zu der Sprache dieses Akzeptors gehören. Könnte man führende Nullen vermeiden?

1. Ergänzen Sie den Automat so, dass er auch Zahlen in Exponentialschreibweise akzeptiert, z.B. 3,143E-02
2. Entwickeln Sie einen Akzeptor, der vorzeichenlose Binärzahlen akzeptiert. Keine führenden Nullen!
3. In der Theologie des Thomas von Aquin ist die Seele ein wunderbar ausgeklügelter Automat. Erschaffen im Stand der Schuld infolge der Erbsünde gelangt sie durch die Taufe in den Stand der Gnade. Gewisse Handlungen (Gotteslästerung, Ehebruch, Mord) bewirken einen Fall in den Stand der Schuld. Beichte, Reue und Absolution können den Stand der Gnade wieder herstellen. Die Wirkung des Todes hängt entscheidend vom Zustand der Seele im Augenblick des Todes ab: Im Stand der Gnade führt der Tod zur Erlösung, im Stand der Sünde zur Verdammnis.
4. Zeichne den Zustandsgraphen des endlichen Automaten. Kennzeichne Eingabealphabet, Zustände, Startzustand, Übergangsfunktion, Ausgabealphabet, Ausgabefunktion, Endzustände.
5. Das folgende Bild zeigt einen Akzeptor.

Welche der folgenden Worte werden vom Automaten akzeptiert? a (2) ab (3) aaabbb (4) ababab (5) baba Finde drei Worte, die nicht oben vorkommen, die vom Automaten akzeptiert werden. Beschreibe mit Worten die Sprache, die vom Automaten akzeptiert wird.