Automaten
In der Informatik versteht man unter einem Automaten das Modell einer digitalen und zeitdiskreten Maschine. Einer solchen Maschine werden Zeichen aus einem Alphabet (digitale Eingabe) zur schrittweisen Verarbeitung (zeitdiskrete Arbeitsweise) vorgelegt. Je nach Modell kann die Maschine in jedem Schritt verschiedene Aktionen ausführen.
Ob es möglich ist, eine solche Maschine technisch zu realisieren, ist in der Automatentheorie zunächst unerheblich. Vielmehr handelt es sich bei einem Automaten um ein gedankliches Modell, das es ermöglicht, ein bestimmtes Verhalten formal und präzise zu beschreiben.
Der Automatenbegriff ist elementar für die theoretische Informatik. So wird der Begriff der Berechenbarkeit mit Hilfe eines Automatenmodells definiert. Auf diese Weise geht man die Frage an, was Computer grundsätzlich zu leisten vermögen. Untersucht man die Komplexität von Algorithmen, dann interessiert man sich vor allem dafür, inwieweit sich diese praktisch umsetzen lassen. Was nützte schließlich der eleganteste Algorithmus, wenn ein entsprechendes Programm siebzehn Milliarden Jahre brauchen würde, um ein Ergebnis zu liefern? Auch dafür sind Automaten überaus hilfreich.
Automaten spielen aber nicht nur in der theoretischen Information eine wichtige Rolle. Die Theorie der formalen Sprachen und die Automatentheorie bilden die Grundlage für den Compilerbau. Auch zur Modellierung von Hardwarekomponenten, Rechnernetzen und verteilten Systemen sind Automaten hervorragend geeignet. Darüber hinaus können Automaten oft sinnvoll eingesetzt werden, um eine Softwarespezifikation präzise und unmissverständlich zu formulieren. Die in diesem Kapitel vorgestellten Grundlagen sind also auch für die technische, praktische und angewandte Informatik von großer Bedeutung. An dieser Stelle wird besonders deutlich, dass das Teilgebiet der theoretischen Informatik das Fundament der gesamten Wissenschaft der Informatik bildet.
In den folgenden Abschnitten werden wir das zunächst das Basismodell der Zustandsmaschine beschreiben, dieses um die Möglichkeit einer Ausgabe erweitern und schließlich spezielle Automatenmodelle, die sich in der gängigen Fachliteratur finden, vorstellen und auf ihre Leistungsfähigkeit untersuchen.
