Endlicher Automat als Registermaschinenprogramm
Dieser endliche Automat hat das Alphabet A = {a, b} (repräsentiert durch die
Ziffern 1 und 2), die Zustände S = {0, 1, 2, 3}, den Startzustand s0
= 0, und die akzeptierten Zustände F = {0}. Akzeptierte Wörter sind zum
Beispiel: 
(das leere Wort), „ab“, „ba“, „abab“ oder
„abba“. Zurückgewiesen werden zum Beispiel „a“, „b“, „aabb“ oder „bbaa“.
Um Wörter beliebiger Länge verarbeiten zu können, muss man die ursprüngliche Registermaschine ein wenig erweitern, damit diese Zeiger auf Speicheradressen unterstützt.
-- Befehlserweiterung! Wert aus Register mit der Nummer, die in Register a
-- steht, laden
exec (PLoad a) (b:c0:c) = if c!!(a-1) > (length c)
then error "index too large at pload"
else (b+1):c!!((c!!(a-1))-1):c
Das eigentliche Programm befindet sich in der Variable ea1asm:
-- Einige Adressdefinitionen, damit man diese nicht immer wieder von Hand
-- ändern muss
stateaddr :: Int
stateaddr = 1
charaddr :: Int
charaddr = 2
-- Das eigentliche Programm
ea1asm :: Program
ea1asm = [
-- Übergangsfunktion
PLoad charaddr, -- Neues Zeichen laden; Dies ist eine (kleine)
-- Befehlserweiterung, da sonst keine Wörter mit
-- variabler Länge verarbeitet werden können
IfGoto 44, -- Ende des Wortes erreicht: Aktuellen Zustand auswerten
CSub 1, -- Entspricht aktuelles Zeichen dem 'a' (== 1)?
IfGoto 8,
PLoad charaddr, -- Zeichen nochmal laden (denn es wurde oben eventuell
-- verändert
CSub 2, -- Ist aktuelles Zeichen ein 'b'?
IfGoto 18,
-- Zeichen ist a
-- Noch ein paar Worte zur Technik des Vergleichens, die ich hier
-- anwende: Die Registermaschine kennt keinen Befehl if $var == 3; sie
-- kann nur zwischen Null und „dem Rest“ entscheiden. Deshalb muss man
-- den entsprechenden Wert abziehen, und schauen, ob das Ergebnis
-- gleich Null ist. Dabei ist es wichtig, zunächst die kleineren und
-- dann die größeren Werte abzuziehen, da z.B. 2 minus 3 (also Wert 2,
-- prüfen ob er 3 ist) nicht wie erwartet -1, sondern auch Null ergibt,
-- denn die Registermaschine kennt keine negativen Zahlen. Eine
-- Befehlssatzerweiterung wäre natürlich auch möglich, aber das ist
-- doch langweilig…
Load stateaddr, -- Aktuellen Zustand herausfinden
IfGoto 31, -- Zustand 0 => Zustand 1
CSub 1, -- Zustand 1 => Zustand 3 (10)
IfGoto 37, -- Und weiterspringen um aktuellen Zustand zu ändern
Load stateaddr,
CSub 2, -- Zustand == 2
IfGoto 28,
Load stateaddr,
CSub 3, -- Zustand 3
IfGoto 37,
-- Zeichen ist b
Load stateaddr,
IfGoto 34, -- Zustand 0 => Zustand 2
CSub 1, -- (20)
IfGoto 28,
Load stateaddr,
CSub 2,
IfGoto 37,
Load stateaddr,
CSub 3,
IfGoto 37, -- Zustand 3 => Zustand 3
-- Zustand ändern
CLoad 0, -- => 0
Store stateaddr,
Goto 40, -- (30)
CLoad 1, -- => 1
Store stateaddr,
Goto 40,
CLoad 2, -- => 2
Store stateaddr,
Goto 40,
CLoad 3, -- => 3
Store stateaddr,
Goto 40,
-- Zeiger auf nächstes Zeichen setzen
Load charaddr, -- (40)
CAdd 1,
Store charaddr,
Goto 1, -- Wieder von vorne anfangen, neues Zeichen auswerten
-- Aktuellen Zustand auswerten
Load stateaddr,
IfGoto 48, -- Zustand ist == 0 und damit akzeptiert
CLoad 0, -- andernfalls ist der Zustand nicht akzeptiert
End,
-- Rückgabewert 1, Programm beenden
CLoad 1, -- 1 signalisiert, dass der Zustand akzeptiert ist
End
]
ea1state :: Config
ea1state = [1, 0, -- Befehls-ID und c_0
0, -- Aktueller Zustand des Automaten
3, -- Aktuelle Zeichenadresse ("An welcher Stelle im Wort sind wir
-- gerade")
1, 2, 2, 1, 0 -- das Wort, abgeschlossen mit 0 (vergleichbar mit
-- Null-Byte bei C-Strings)
]
Das Haskell-Programm lässt sich zum Beispiel mit hugs mit dem Kommando rm ea1asm ea1state ausführen. Das Ergebnis ist mit der oben angegebenen Anfangskonfiguration [49,1,0,7,1,2,2,1,0]. „abba“ ist also akzeptiert, denn c0 ist gleich 1.