Kleines Nachschlagewerk Informatik
Grundlagen
Worum geht es?
Zuerst soll das Prinzip der Automaten kurz dargestellt werden und gezeigt werden, warum dieses Modell sinnvoll ist.
Was sind Automaten?
Die einfachsten programmierbaren Systeme sind sicher Steuerungen, die nur Eingaben (Lochstreifen etc.) abarbeiten und diese direkt in Steuerbefehle umsetzen. Diese Maschinen können aber z.B. nicht rechnen, weil sie sich nichts merken können.

Der nächste Schritt sind Maschinen, die einen Zustand haben. Je nach Zustand reagieren sie unterschiedlich auf eine Eingabe. Der Kugelschreiber reagiert auf die Eingabe "Druck" unterschiedlich, je nachdem, ob die Mine drin war oder draußen.

Möchte man das System noch komplexer gestalten, fügt man Speicher hinzu.

Zustandsbasierte Systeme mit oder ohne Speicher bezeichnet man als Automaten. Man kann sie in verschiedene Kategorien einteilen, was im folgenden auch getan wird.
Warum Automaten?
Derartig einfache programmierbare Systeme und ihr Verhalten lassen sich so am besten beschreiben. Man möge bitte bedenken: Wir sind hier am Anfang einer langen Reise. Bis zur klassischen Programmiersprache ist es noch ein weiter Weg.

Dies ist sozusagen für die Informatik das, was die Zahlentheorie für die Mathematik ist.
Wie stellt man Automaten dar?
Die zugänglichste Form ist ein Graph mit Zuständen, wobei die Zustandsübergänge durch den entsprechenden Zeichen gekennzeichnet sind.





Möchte man eine exakte formale Definition angeben, braucht man:

Manche Automaten haben Wie dies alles konkret aussieht, zeigt sich bei der Behandlung der verschiedenen Automaten.
Deterministische und nichtdeterministische Automaten
Man kann Automaten in deterministische und nichtdeterministische unterscheiden. Erstere kennzeichnen eindeutige Zustandswechsel. Somit ist es bei nichtdeterministischen Automaten möglich, durch Verarbeiten eines Zeichens in zwei verschiedene Zustände zu springen (was bedeutet, dass beide Varianten getestet werden müssen).

Nichtdeterministische Automaten lassen sich jedoch in deterministische überführen. Bei den endlichen Automaten wird eine solche Umwandlung gezeigt.
Automaten und Maschinen
Die Literatur ist nicht eindeutig in Bezug auf Automaten und Ausgaben. Oft wird ein Automat mit Ausgabe als Maschine bezeichnet. In der schulnahen Literatur findet man aber auch oft Automaten mit Ausgaben.

Aus diesem Grund und weil zu vermuten ist, dass Abituraufgaben ebenfalls Automaten mit Ausgabe bevorzugen, machen wir dies ebenso. Die Ausgaben sind dabei an den Zustandswechsel gebunden. Somit bezeichnen wir Mealy-Maschinen als Automaten.