Übersicht Automaten

Ein Automat ist in der Informatik eine gedachte Maschine

 

1. Übersicht Automaten

Ein Automat ist in der Informatik eine gedachte Maschine (also abstrakte Modelle von Maschinen), die sich gemäss bestimmter Regeln verhält. Sie dienen in der Theoretischen Informatik als Konstrukt, um gewisse Eigenschaften von Problemen und Algorithmen zu analysieren und zu beweisen. Dabei sind die Automaten meistens möglichst einfach strukturiert, so dass sich leicht mit ihnen Argumentieren lässt - ob es tatsächleich möglich oder sinnvoll wäre, eine soche Maschine zu bauen, ist dabei zunächst unerheblich.


Die Automaten sind meist ähnlich aufgebaut: Der Automat hat einen inneren Zustand und bekommt eine Eingabe, die (meistens) Zeichen für Zeichen gelesen werden. Eine Zustandsübergangstabelle definiert, abhängig vom aktuellen Zustand und dem gerade gelesenen Zeichen, den nächsten Zustand.

Automaten werden unter anderem in deterministischeund nichtdeterministische unterschieden. Dabei ist bei nichtdeterministische Automaten nicht eindeutig vorherbestimmt, welcher Zustand auf welchen Anderen folgt - der Automat kann so effektiv raten. Dabei gilt ein Problem schon dann durch einen nichtdeterministische Automaten gelöst, wenn er das Ergebnis in dem Fall findet, dass er immer richtig rät. Oder man könnte sagen, ein solcher Automat würde alle Möglichkeiten parallel probieren.

Bekannte Typen von Automaten sind:
  • Endliche Automaten: akzeptieren die Reguläre Sprachen
  • Kellerautomaten: akzeptieren die Kontextfreie Sprachen
  • Turingmaschinen: definieren den Begriff der Berechenbarkeit.
  • Registermaschinen: sind genau so mächtig wie Turingmaschinen, bieten aber in einigen Fällen ein besseres Maß für die Zeitkomplexität.
Von praktische Relevanz in der Programmierung sind vor allem Endliche Automaten und Kellerautomaten: sie bieten eine einfache Struktur, mit der sich viele komplexe Probleme übersichtlich lösen lassen.