Registermaschine

Quelle: https://arbeitsplattform.bildung.hessen.de/fach/informatik/registermaschine.html

In der Literatur werden verschiedene Varianten von Registermaschinen beschrieben. Im Hinblick auf das Landesabitur ist deshalb ein einheitliches Modell erforderlich, das als Grundlage für Abituraufgaben verwendet wird. Dieses Modell orientiert sich am Buch Theoretische Informatik von A. Asteroth und C. Baier, weist aber einige Unterschiede auf.

Eine Registermaschine besteht aus unendlichen vielen Registern R1, R2, R3,…, in denen natürliche Zahlen gespeichert werden. Sie verfügt zusätzlich über einen Akkumulator, der das Ergebnis des jeweils letzten Rechen- oder Ladebefehls enthält. Die Arbeitsweise wird durch ein Programm angegeben. Dieses setzt sich aus einer Folge von einzelnen Befehlen zusammen, die zeilenweise untereinander geschrieben werden. Programmzeilen kann man mit einer Marke versehen, um Sprünge dorthin ausführen zu können.

Die Registermaschine hat die Befehle: LOAD, STORE, ADD, SUB, MUL, DIV, GOTO, JZERO, JNZERO und END. Bei den Sprungbefehlen wird als Operand eine Marke angegeben. Bei den arithmetischen Befehlen und den Speicherbefehlen sind drei Arten von Operanden zulässig:

	Operand	Bedeutung	Beispiel
Konstanten	#i	der Operand ist die Zahl i	LOAD #7
direkte Adressierung	i	der Operand ist das Register i	ADD 4
indirekte Adressierung	*i	der Operand ist das Register, dessen Nummer im Register i steht	STORE *3

In der folgenden Befehlsübersicht bedeutet x den jeweiligen Operanden:

Befehl	Bedeutung
LOAD x	Lädt x in den Akkumulator
STORE x	Speichert den Inhalt des Akkumulators in x. Dabei darf x keine Konstante #i sein.
ADD x	Addiert x zum Akkumulator
SUB x	Subtrahiert x vom Akkumulator. Ist der Wert von x größer als der des Akkumulators, ist das Ergebnis 0.
MUL x	Multipliziert x mit dem Akkumulator.
DIV x	Dividert den Akkumulatorinhalt durch x. Für x = 0 wird das Programm beendet.
GOTO M	Ein unbedingter Sprung zur Marke M.
JZERO M	Falls der Akkumulator den Wert 0 hat, erfolgt ein Sprung zur Marke M.
JNZERO M	Falls der Akkumulator einen Wert größer 0 hat, erfolgt ein Sprung zur Marke M.
END	Das Programm wird beendet.

Beispiel 1:

Registermaschine für die Berechnung von n^m.

Registerbelegung

R1	n
R2	m
R3	Ergebnis

Programm

 	LOAD #1	// Initialisierung mit Ergebnis = 1
 	STORE 3	 
M1:	LOAD 2	// lade Exponent
 	JZERO Ende	// m = 0, Berechnung fertig
 	SUB #1	// m = m - 1
 	STORE 2	 
 	LOAD 3	 
 	MUL 1	// Ergebnis = Ergebnis * n
 	STORE 3	 
 	GOTO M1	// nächster Schleifendurchlauf
Ende:	END

Beispiel 2:

Diese Registermaschine akzeptiert die Sprache L = { aⁿbⁿ | n ∈ Ν }. Sie erhält ein Wort w über dem Alphabet E = {a, b} als Eingabe und entscheidet, ob es die Form aⁿbⁿ hat. Das erste Zeichen von w wird im ASCII-Code im Register R4 gespeichert, alle weiteren in den darauffolgenden Registern. a hat den ASCII-Code 141 und b die 142.

Registerbelegung

R1	Eingabeposition, Anfangswert 4
R2	Anzahl a - Anzahl b
R3	Ausgabe 1 für akzeptiert, 0 für nicht akzeptiert
R4...	das Eingabewort

Programm

 	 LOAD #4	// R1 initialisieren
 	 STORE 1	 
 	 LOAD #0	// R2 und R3 initialisieren
 	 STORE 2	 
 	 STORE 3	 
AZählen: LOAD *1	 
 	 JZERO Fertig	// Ende der Eingabe
 	 SUB #141	 
 	 JNZERO BZählen	// kein a mehr
 	 LOAD 2	 
 	 ADD #1	 
 	 STORE 2	 
 	 LOAD 1	        // nächstes Zeichen
 	 ADD #1	 
 	 STORE 1	 
 	 GOTO AZählen	 
BZählen: LOAD *1	 
 	 JZERO Fertig	// Ende der Eingabe
 	 SUB #141	 
 	 JZERO Ende	// ein a nach einem b
 	 LOAD 2	 
 	 JZERO Ende	// mehr b als a
 	 SUB #1	 
 	 STORE 2	 
 	 LOAD 1	        // nächstes Zeichen
 	 ADD #1	 
 	 STORE 1	 
 	 GOTO BZählen	 
Fertig:	 LOAD 2	 
 	 JNZERO Ende	 
 	 LOAD #1	 
 	 STORE 3	 
 Ende:	 END