Hessischer Bildungsserver / Arbeitsplattformen

Registermaschine

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 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: Registermaschine als Akzeptor für anbn.

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  

 

Simulationsprogramm

Herr Norman Sutatyo hat das Simulationsprogramm remasp (Version 3.2 vom 21.08.2019) geschrieben, mit dem Registermaschinenprogramme schrittweise ausgeführt werden können.