Endlicher Automat als Registermaschinenprogramm
===============================================

.. image:: ../../media/00/14/ea1.thumb.jpg
	:alt: Schaubild: Endlicher Automat
	:align: right
	:target: ../../media/00/14/ea1.png

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\ :sub:`0`
= 0, und die akzeptierten Zustände F = {0}. Akzeptierte Wörter sind zum
Beispiel: :eqn:`\\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 :doc:`15:
ursprüngliche Registermaschine` ein wenig erweitern, damit diese Zeiger auf
Speicheradressen unterstützt.

.. code-block:: haskell

	-- 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``:

.. code-block:: haskell

	-- 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\ :sub:`0` ist gleich 1.