In diesem Kapitel lernen wir mit den endlichen Automaten ein erstes Berechnungsmodell kennen. Dieses Modell orientiert sich am Rechnen mit begrenztem Speicher. Wir werden sehen, dass wir nur sehr einfache Probleme mit einem endlichen Automaten lösen können. Trotzdem ist der endliche Automat ein sehr wichtiges Modell, denn er bildet die Grundlage für weitere Modelle und findet als Modellierungswerkzeug in der gesamten Informatik vielfältige Anwendungen. Im weiteren Verlauf betrachten wir das Problem der Minimierung von endlichen Automaten.Wir stellen dazu ein Verfahren vor, dass einen Automaten so umformt, dass er die minimale Anzahl von Zuständen hat (und dabei die gleiche Sprache erkennt). Um diese Konstruktion zu verstehen, tauchen wir etwas tiefer in die Theorie der regulären Sprachen ein, und untersuchen deren Myhill–Nerode Relationen.