Automatentheorie
Die Hierarchie der Automatentheorie dient schon lange als bewährter Maßstab der Mächtigkeit von Computing-Paradigmen. Sie steht wiederum in einer engen – und durchaus praxisrelevanten! – Korrespondenz zur Chomsky-Hierarchie der formalen Sprachen.
Endliche Automaten – finite automaton (FA) = finite state machine (FSM) – stellen die unterste Stufe in dieser Hierarchie dar. Man kann sie sich als eine einzige Variable vorstellen, den Zustand (state), und eine Tabelle mit endlich vielen Zeilen und Spalten. In der Zeile, die durch die Zustandsvariable bestimmt ist, wird die Spalte ausgelesen, die dem Signal oder Eingabesymbol entspricht, das der endliche Automat empfängt.
Der Inhalt dieser Zelle bestimmt die Reaktion des Automaten – also den neuen Zustand und die eventuelle Ausgabe -, salopp formuliert wie eine (potenziell sehr komplexe) Waschmaschine. Reguläre Sprachen sind die unterste Ebene der Chomsky-Hierarchie und können von endlichen Automaten akzeptiert werden. (Ein FA kann also feststellen, ob eine Input-Sequenz zu seiner regulären Sprache gehört.) Praktisch relevant sind FA für einfache Parser und reguläre Ausdrücke (REGEX).
Darüber stehen die sogenannten Stack- oder Keller-Automaten. Hier wird ein endlicher Automat um einen externen Speicher in Form eines Stacks oder Stapelspeichers erweitert, der in die Reaktion eingebunden wird. Also etwa wie Taschenrechner, die den korrekten arithmetischen Operatoren-Vorrang und die Klammerung beherrschen oder gleich in UPN arbeiten.
Stellt man sich den Operator-Vorrang durch explizite Klammerung mit eckigen Klammern vor, so hat man eine Dyck-Sprache mit zwei Klammerntypen – ein Musterbeispiel für die kontextfreien Sprachen – und sieht unmittelbar die Notwendigkeit des Stacks: Um zu wissen, was die korrekte nächste schließende Klammer wäre – "]" oder ")" -, müssen die öffnenden Klammern auf den Stack gelegt werden.
Typische Programmiersprachen enthalten mit ihren Schleifen- und Verzweigungsstrukturen ebenfalls logisch verschiedene Klammern, und so wundert es nicht, dass Stack-Automaten praktisch relevant für den Compiler-Bau sind. (Es gibt da noch einen lästigen kleinen Unterschied zwischen der Mächtigkeit deterministischer und nichtdeterministischer Stack-Automaten, den wir uns hier schenken.) Die meisten natürlichen Sprachen sind mit einer kontextfreien Grammatik beschreibbar, aber nicht alle: Schwyzerdütsch und Niederländisch etwa.
Die oberste Stufe der Hierarchie nehmen die Turing-Maschinen ein: Der Lesekopf ist – die aufmerksamen Leser ahnen es – ein endlicher Automat, der in der beschriebenen Weise auf dem deutlich mächtigeren externen Speicher in Form des endlosen Bandes arbeitet. Sie akzeptieren die höchste Stufe der Chomsky-Hierarchie, die rekursiv aufzählbaren Sprachen.
Es gibt noch sehr viel mehr Abstufungen durch Automatenkonzepte mit subtilen Unterschieden. Eines verdient noch Erwähnung: die linear beschränkten Automaten. Das sind Turing-Maschinen, deren Bandlänge auf ein Vielfaches der Länge der Eingabe beschränkt ist. Diese Einschränkung ist etwas schärfer als mein "endlich, aber ausreichend langes Band".
Sie sind zwischen Stackautomaten und Turingmaschinen zu verorten und akzeptieren die kontextsensitiven Sprachen, allerdings ist das nur für die nichtdeterministische Variante bewiesen. Ob es auch für die deterministische Variante gilt oder ob diese nur eine Teilmenge akzeptiert, ist ein ungelöstes theoretisches Problem.
- Anzeige Hier geht es zu Künstliche Intelligenz: Wissensverarbeitung bei Amazon Wenn Sie auf diesen Link klicken und darüber einkaufen, erhält Golem eine kleine Provision. Dies ändert nichts am Preis der Artikel.