Endliche Automaten und Mealy-Automaten
Deterministische endliche Automaten (DEA) funktionieren nach einem klaren Prinzip: Für jeden Zustand und jede Eingabe ist eindeutig festgelegt, wohin der Automat als nächstes wechselt. Das bedeutet, es darf keine mehrfachen Pfeile mit gleicher Beschriftung oder leere Übergänge geben.
Ein DEA besteht aus einem 5-Tupel: endliche Menge an Zuständen, Eingabealphabet, totale Überführungsfunktion, Anfangszustand und endliche Menge an Endzuständen. Diese Struktur macht den Automaten vorhersagbar und eindeutig.
Mealy-Automaten erweitern das Konzept um Ausgaben. Hier wird jedem Übergang nicht nur eine Eingabe, sondern auch eine Ausgabe zugeordnet (x/y-Notation). Der Automat benötigt dabei keinen Endzustand, da er kontinuierlich Ausgaben produziert.
Wichtig: Endliche Automaten haben klare Grenzen - sie können keine beliebig große Datenmenge speichern oder bereits erfolgte Ein-/Ausgaben merken. Probleme wie das Erkennen korrekt geschachtelter Klammern sind damit nicht lösbar.
