Ü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.

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.

• 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.

Womit beschäftigt sich die theoretische Informatik?
Sowohl für die Konstruktion von Algorithmen als auch für die Konstruktion von Computern spielen Methoden und Modelle aus der Mathematik eine wichtige Rolle. In der Mathematik werden aber überwiegend statische Strukturen betrachtet, in der Informatik dynamische (Prozesse).
Ein wichtiger Grundbegriff der Informatik ist der Begriff des Algorithmus. Die theoretische Informatik beschäftigt sich vor allem mit der Fundierung des Algorithmusbegriffs, untersucht die Leistungsfähigkeit von Algorithmen und erforscht die prinzipiellen Grenzen des Computers beim Lösen von Problemen.
Teilgebiete der theoretischen Informatik sind insbesondere:

• Theorie der formalen Sprachen,
• Automatentheorie,
• Algorithmentheorie,
• Berechenbarkeitstheorie,
• Komplexitätstheorie.

Theorie der formalen Sprachen
Damit Algorithmen durch Computer abgearbeitet werden können, müssen sie in einer Programmiersprache niedergeschrieben sein. Die Theorie der formalen Sprachen beschäftigt sich mit der Konstruktion von Programmiersprachen, allerdings ausschließlich mit deren Syntax. Die Bedeutung (die Semantik) spielt keine Rolle.
Unter Syntax versteht man die Lehre vom Satzbau. Sie umfasst sämtliche grammatikalischen Regeln, deren Anwendung zu korrekt gebauten Sätzen führt. Die Menge aller aus einer formalen Grammatik herleitbaren Sätze bildet die Menge der Sätze einer Sprache. Ein Satz kann also ein Teil eines Programms oder sogar ein vollständiges Programm sein.

Automatentheorie
In der Informatik bezeichnet man als Automaten die mathematischen Modelle von (technischen) Geräten, die Daten verarbeiten und auf Eingaben reagieren, wobei die Eingabegrößen nicht verändert werden dürfen. Die technische Realisierung solcher gedanklichen Modelle sind letztlich Computer.
Die Automatentheorie beschäftigt sich mit der Untersuchung der mathematischen Modelle von Computern. Automaten werden auch zur Beschreibung, Erkennung und Übersetzung von formalen Sprachen genutzt.

Algorithmentheorie
Ein Algorithmus ist eine eindeutig ausführbare Verarbeitungsvorschrift, die für eine Klasse von Problemen gilt, also für diese Klasse allgemeingültig ist, und nach endlich vielen Schritten zum Ziel führt. Dies ist eine sehr verschwommene Definition. Ein Algorithmus muss in der Notationsform „Programm“ so präzise formuliert sein, dass er von einem elektronisch arbeitenden Gerät (Computer) korrekt ausgeführt werden kann.
Algorithmen können durch Automaten (s. Automatentheorie), aber auch als berechenbare Funktionen (s. Berechenbarkeitstheorie) beschrieben werden.
Die Algorithmentheorie beschäftigt sich mit der mathematisch exakten Beschreibung, Untersuchung und Klassifizierung von Algorithmen.

Berechenbarkeitstheorie
Einen Algorithmus kann man auch als Abbildung betrachten, als eine Funktion, die Eingabedaten auf Ausgabedaten abbildet. Nicht jede mögliche Abbildung lässt sich durch einen Algorithmus beschreiben. Historisch gesehen hat man zunächst versucht, genau diejenigen Abbildungen zu definieren, die von Algorithmen beschrieben werden. Solche Abbildungen heißen berechenbare Funktionen.
Die Berechenbarkeitstheorie beschäftigt sich mit Algorithmen auf der Basis berechenbarer Funktionen.

Komplexitätstheorie
Die Komplexitätstheorie untersucht die Komplexität von Funktionen und Algorithmen, das heißt den notwendigen Rechenaufwand und Aufwand an Speicherplatz. Insbesondere werden auch Komplexitätsklassen (Aufwandsklassen) ausgegliedert und algorithmisch beschreibbare Probleme diesen Klassen zugeordnet.
Die Untersuchung erfolgt unabhängig von speziellen Computern. Man nutzt als formale Berechnungsmodelle gedankliche Automatenmodelle (s. Automatentheorie), insbesondere so genannte Turingmaschinen (mit mehreren Bändern) und Registermaschinen (oft als parallele Maschinen).

Ein endlicher Automat liest eine endliche Folge von Symbolen, das Eingabewort, aus einer endlichen Menge von Symbolen, dem Eingabealphabet, und schreibt gemäß seiner Programmierung eine endliche Folge von Symbolen, das Ausgabewort, aus einer Menge von Symbolen, dem Ausgabealphabet.

Beim Lesen der Eingabe und Schreiben der Ausgabe geht der Automat schrittweise vor, wobei er in jedem Schritt das jeweils nächste Symbol des Eingabewortes liest. Abhängig von diesem Eingabesymbol und des momentanen Zustandes produziert er dann in einem Bearbeitungsschritt eine endliche Folge von Ausgabesymbolen (und erweitert so die Ausgabe) und geht in einen neuen Zustand über.

Akzeptieren der Reguläre Sprachen

Eine einfachere Variante, die man auch häufig als endlicher Akzeptor bezeichnet, produziert dagegen keine Ausgabe, sondern stoppt nach dem vollständigen Lesen der Eingabe entweder in einem akzeptierenden oder einem nichtakzeptierenden Zustand.

Als Modell für alle diese Systeme wählen wir die folgende Beschreibung:
Der Automat bestehe aus einer Maschine, die verschiedene interne Zustände einnehmen kann.
Er verfüge darüber hinaus über einen Lesekopf, an dem ein Eingabeband in nur einer Richtung vorbeigeführt wird (wie bei einem Tonband oder einem Lochstreifenleser). Auf dem Eingabeband stehen nacheinander die Eingabezeichen, die in beliebiger Folge aus dem Eingabealphabet gewählt werden können. In Abhängigkeit vom zuletzt gelesenen Eingabezeichen
und dem momentanen Zustand geht der Automat in einen Folgezustand über, nachdem er ein Ausgabezeichen, das zum Ausgabealphabet gehört, produziert hat. Dieses Ausgabezeichen wird von einem Schreibkopf auf ein Ausgabeband geschrieben, das sich ebenfalls nur in einer Richtung am Schreibkopf des Automaten vorbeibewegt, also nach jedem Schreibvorgang um eine Position weiterrückt.

Die Reaktion des Automaten auf das jeweilige Eingabezeichen wird präzise durch zwei Funktionen festgelegt: Die Überführungsfunktion u bestimmt aus Eingabezeichen und Zustand den Folgezustand. Die Ausgabefunktion g bestimmt aus Eingabezeichen und Zustand das Ausgabezeichen. Beide Funktionen sind sowohl im Zustandsdiagramm wie in der Zustandstabelle enthalten.

Quelle: Eckart Modrow Einführung in die technische Informatik

Walter Gussmann () Workshop: Automaten und Sprachen 11. Dezember 2007

Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes mathematisches Modell.

• einem unendlich langen Speicherband mit unendlich vielen Feldern. In jedem dieser Felder kann genau ein Zeichen gespeichert werden.
• einem Schaltwerk mit endlich vielen Zuständen. Es steuert das Verhalten der Turingmaschine.
• einem programm-gesteuerten Lese- und Schreibkopf, der auf dem endlosen Speicherband ein Feld nach links oder rechts rücken, ein Zeichen lesen, schreiben oder löschen und stehen bleiben kann.

Das faszinierende an einer Turing-Maschine ist, dass sie mit nur 3 Operationen (lesen, schreiben und Kopf bewegen) alle lösbaren Probleme lösen kann. Sämtliche mathematischen Grundfunktionen, wie Addition und Multiplikation lassen sich mit diesen 3 Operatoren simulieren. Aufbauend darauf lassen sich wiederum sämtliche restlichen vorhandenen mathematischen Funktionen erzeugen, usw.

Der zentrale Satz ist also: Ein Problem, das man mit einer Turingmaschine nicht lösen kann, gilt auch allgemeinhin als unlösbar.