Grundlagen zu Automaten


Automaten trifft man heutzutage überall im Alltag wieder. Sei es im Bahnhof am Fahrkartenautomat, in der Universität beim Getränkeautomat oder in der Bank beim Geldautomat. Automaten kosten deren Betreiber nicht nur keine Personalkosten, sie sind darüber hinaus auch zu jeder Tageszeit betriebsbereit.


Damit ein Automat auch funktioniert, besitzt er unterschiedliche Objekte, Zustände und Funktionen. So hat ein realer Automat beispielsweise Eingabeobjekte (Geldstücke, Tastendrücke …) oder auch Ausgabeobjekte (Getränke, Fahrkarte, Rückgeld …). In Zusammenhang mit diesen Objekten stehen Funktionen, die Zustände ändern oder auch Ausgaben bewirken können. Jeder Automat sollte einen Startzustand besitzen. Darüber hinaus kann auch ein Endzustand existieren. Dieser ist aber nicht zwingend erforderlich.


Ein wesentlicher Aspekt eine jeden endlichen Automaten ist die Eingabe und die Ausgabe. Während die Eingabe zu Zustandsänderungen führt, gibt der Automat bei der Ausgabe etwas aus. Für Eingabe und Ausgabe steht dafür ein entsprechendes Alphabet bereit. Über dieses Alphabet lässt sich mit der Menge aller akzeptierten Eingabefolgen (Wörter) eine Sprache des Automaten bilden.


Ein endlicher Automat wird durch ein Zustandsübergangsdiagramm graphisch dargestellt. Dabei stellen Kreise die Zustände dar (in jedem Kreis steht der Name des Zustands). Zwischen den Kreisen gibt es Pfeile, die Transitionen darstellen. Dabei steht bei jedem Pfeil welche Bedingung den Übergang ermöglicht.

Zitat:



Edsger Wybe Dijkstra:

"Als es noch keine Computer gab, gab es auch das Programmieren als Problem nicht. Als es dann ein paar leistungsschwache Computer gab, wurde das Programmieren zu einem kleinen Problem und nun, wo wir leistungsstarke Computer haben, ist auch das Programmieren zu einem riesigen Problem angewachsen. In diesem Sinne hat die elektronische Industrie kein einziges Problem gelöst, sondern nur neue geschaffen." - The Humble Programmer, ACM Turing Lecture 1972