Die theoretische Informatik ist ein Teilgebiet der Informatik, welche sich mit grundlegenden Fragestellungen der Informatik befasst. Unter anderem ist auch die Automatentheorie Inhalt dieses Teilgebiets.
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. Diesen speziellen Automaten nennt man Mealy-Automat.
Fassen wir das noch mal allgemein zusammen
Ein endlicher Automat besteht aus
Ü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 (-)“.