Automat

From Glottopedia
Jump to navigation Jump to search
REF This article has no reference(s) or source(s).
Please remove this block only when the problem is solved.


In der Mathematik, Kybernetik, Linguistik, Informatik und Informationstechnologie ist ein Automat ein abstrakte Maschine, welche sich gemäß bestimmten Regeln bzw. nach einem Programm verhält. Ein Automat geht in Abhängigkeit vom aktuellen Zustand und der aktuellen Eingabe von einem in einen neuen Zustand über. Die Menge der möglichen Zustandsübergänge (Transitionen), die das Verhalten des Automaten definiert, kann als das Programm des Automaten verstanden werden. Ein Automat ist definiert durch die Menge der Zustände, die möglichen Eingabezeichen (das sog. Eingabealphabet), die Übergangsfunktion (d.h. wann der Automat in welchen Zustand übergeht), den Startzustand und die Menge der Endzustände.

Beispiel

Ein gutes Beispiel für einen Automaten aus dem alltäglichen Leben ist ein Getränkeautomat. Bei Einwurf des passenden Geldbetrags geht dieser Automat vom passiven Zustand in den Zustand der Getränkeausgabe über.

Deterministische und nichtdeterministische Automaten

Wenn durch den aktuellen Zustand des Automaten und das jeweilige Eingabezeichen der Folgezustand eindeutig gegeben ist, dann handelt es sich um einen deterministischen Automaten. Es ist aber auch möglich dem Automaten verschiedene Freiheitsgrade bei den Zustandsübergängen zu geben. Solch ein nicht deterministischer Automat kann dann von einem bestimmten Zustand und einem Eingabezeichen willkürlich in verschiedene Folgezustände übergehen. Es kann außerdem auch noch spontane Zustandsübergänge geben, welche ohne Eingabezeichen stattfinden (ε-Übergänge).

Kommentare

Es gibt verschiedene Klassen oder Typen von Automaten, die nach den Mitteln, die ihnen zur Verfügung stehen, unterschieden werden. Jeder Klasse von Automaten entspricht eine Klasse Formaler Sprachen. Zu den bekanntesten Typen von Automaten gehören die deterministischen Automaten und die nicht-deterministischen Automaten. Eine wichtige Rolle spielen außerdem stochastische Automaten, die den Zustandsübergängen Wahrscheinlichkeiten zuordnen.

Siehe auch