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:

OperandBedeutungBeispiel
Konstanten#ider Operand ist die Zahl iLOAD #7
direkte Adressierungider Operand ist das Register iADD 4
indirekte Adressierung*ider Operand ist das Register,
dessen Nummer im Register i steht
STORE *3

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

BefehlBedeutung
LOAD xLädt x in den Akkumulator
STORE xSpeichert den Inhalt des Akkumulators in x. Dabei darf x keine Konstante #i sein.
ADD xAddiert x zum Akkumulator
SUB xSubtrahiert x vom Akkumulator. Ist der Wert von x größer als der des Akkumulators, ist das Ergebnis 0.
MUL xMultipliziert x mit dem Akkumulator.
DIV xDividert den Akkumulatorinhalt durch x. Für x = 0 wird das Programm beendet.
GOTO MEin unbedingter Sprung zur Marke M.
JZERO MFalls der Akkumulator den Wert 0 hat, erfolgt ein Sprung zur Marke M.
JNZERO MFalls der Akkumulator einen Wert größer 0 hat, erfolgt ein Sprung zur Marke M.
ENDDas Programm wird beendet.

Beispiel 1:

Registermaschine für die Berechnung von nm.

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 = { anbn | n ∈ Ν }. Sie erhält ein Wort w über dem Alphabet E = {a, b} als Eingabe und entscheidet, ob es die Form anbn 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

Schlagwörter: