Automatenmodell
In der theoretischen_Informatik werden zwei Kategorien, nämlich die deterministischen und die nichtdeterministischen Automaten, und drei grundsätzliche Klassen unterschieden, nämlich die endlichen Automaten, die stapelverarbeitenden Kellermaschinen und die mit beidseitig unendlichem Band ausgestatteten Turingmaschinen. Diese Automatenmodelle stehen in einer logischen Beziehung zu den Sprachklassen und finden dort ihre formale Entsprechung.Endlicher Automat
Ein Fahrkartenautomat gehört zur Klasse der endlichen Automaten. Er hat als Eingabealphabet verschiedene Tasten, einen Kartenleser mit endlichem Magnetband und einen einfachen Timer. Er hat einen Anfangszustand mit Willkommensmeldung, reagiert auf die Reihenfolge der Eingaben des genannten Alphabets und erreicht einen Endzustand, wenn die Fahrkarte gedruckt wird.
Kellerautomat
Wenn Spielkarten auf einem Stapel abgelegt werden und in umgekehrter Reihenfolge wieder gezogen werden, ist damit prinzipiell ein endlicher Kellerspeicher realisiert. Nach demselben Prinzip arbeitet auch eine Kellermaschine, jedoch mit unendlichem Stapel. Sie hat ebenfalls ein Eingabealphabet - die Spielkartenbilder - und reagiert programmiert auf diese Eingaben. Sie ist intelligenter als ein endlicher Automat, weil sie über einen unendlichen Speicher, den sogenannten Keller, verfügt. Siehe auch das Beispiel umgekehrte polnische Notation.
Turingmaschine
Wenn man nun auf den unendlichen Stapel der Kellermaschine eine beliebige Zugriffsreihenfolge erlaubt, also Herausgreifen aus der Mitte des Stapels oder etwa der untersten Karte, erhält man einen noch intelligenteren Automaten, welcher nach dem englischen Mathematiker Alan Turing benannt ist. Es ist eine bisher nicht widerlegte These, die Churchsche These, dass man grundsätzlich mit einem solchen Automaten alle denkbaren Berechnungen durchführen kann. In der Praxis wird dieses Modell allerdings so gut wie gar nicht eingesetzt, weil es sehr langsam und speicherhungrig ist und man im Laufe der Jahrzehnte optimierte Methoden der Berechnung entwickelt hat.
Determinismus
Zu allen drei Klassen sind jeweils deterministische, also vorhersagbare, als auch nichtdeterministische, also von vornherein unbestimmbare, nichtdeterministische Modelle vorstellbar. Wenn man jedoch der Unbestimmtheit eines Zustandsüberganges eine gewisse Wahrscheinlichkeit zuordnen kann, kommt man zu stochastischen Automaten bzw. den Markov-Ketten.
Siehe auch
*Chomsky-Hierarchie
*Informatik
