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 s₀ = 0, und die akzeptierten Zustände F = {0}. Akzeptierte Wörter sind zum Beispiel: $\epsilon$ (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 c₀ ist gleich 1.