Extra Lösung 05

Universität des Saarlandes
Fakultät 6.2 – Informatik
Theoretische Informatik (WS 2015)
Team der Tutoren
Aufgaben aus den Übungsgruppen 6(Lösungsvorschläge)
Aufgabe 6.1 (Divergenz)
Entwerfen Sie eine Registermaschine, die divergiert.
Lösungsvorschlag 6.1
L1 :
L2 :
STOP:
x1 = 0 goto L2
i f ( x1 =? 0 ) then goto L1 e l s e goto STOP
Aufgabe 6.2 (Einfache Registermaschinen)
Entwerfen Sie einfache Registermaschinen, die die folgenden Funktionen berechnen:
(
0 falls x = 0
1. sgn : N → N, sgn(x) =
1 falls x > 0
(
0 falls x ≤ y
2
2. grtr : N → N, grtr(x, y) =
1 falls x > y
(
x
falls 3 | x
3. div3 : N → N, div3(x) = 3
⊥ falls 3 - x
Hierbei bedeutet ⊥, dass die Funktion divergiert.
Quelle: Vertiefungsvorlesung „Recursion Theory“, Universität des Saarlandes, Sommersemester 2015, Übungsblatt 1
Lösungsvorschlag 6.2
1.
L1 :
L2 :
L3 :
L4 :
STOP:
if
x1
if
x1
( x1 =?
= x1−1
( x1 =?
= x1+1
0 ) then goto STOP e l s e goto L2
goto L3
0 ) then goto L4 e l s e goto L2
goto STOP
2. Idee: Input (x, y), dekrementiere x und x, bis (x0 , 0) erreicht wird. Gebe 1 zurück, wenn x0 > 0
CHECK1:
CHECK2:
DEC1 :
DEC2 :
SET1 :
SET2 :
L1 :
STOP:
if
if
x1
x2
x1
if
x1
( x2 =?
( x1 =?
= x1−1
= x2−1
= x1−1
( x1 =?
= x1+1
0 ) then goto CHECK2 e l s e goto DEC1
0 ) then goto STOP e l s e goto SET1
goto DEC2
goto CHECK1
goto SET2
0 ) then goto L1 e l s e goto SET1
goto STOP
3.
CHECK1: i f ( x1 =? 0 ) then goto TRANSF e l s e goto DEC1
DEC1 :
x1 = x1−1 goto CHECK2
CHECK2: i f ( x1 =? 0 ) then goto UNDEF e l s e goto DEC2
1/6
DEC2 :
CHECK3:
DEC3 :
GOT3:
UNDEF:
TRANSF:
T1 :
T2 :
STOP:
x1 = x1−1 goto CHECK3
i f ( x1 =? 0 ) then goto UNDEF e l s e goto DEC3
x1 = x1−1 goto GOT3
x2 = x2+1 goto CHECK1
goto UNDEF
i f ( x2 =? 0 ) then goto STOP e l s e goto T1
x2 = x2−1 goto T2
x1 = x1+1 goto TRANSF
Aufgabe 6.3 (Syntaktischer Zucker: Prädikate)
Bisher können wir in Anweisungen der Form L: if P then A else B nur Ps der Form a =? b verwenden.
Simulieren Sie Anweisungen der Form:
1. if x ≥ y then A else B
2. if x > y then A else B
3. if x 6= y then A else B
Lösungsvorschlag 6.3
1. Größer
L1 : xi = y − x goto L2
L2 : i f xi = 0 then A goto NextLine e l s e B goto NextLine
NextLine :
2. Größer-gleich
L0 : xi = y + 1 goto L2
L2 : i f x ≥ xi then A goto NextLine e l s e B goto NextLine
NextLine :
3. Ungleich
L1 : i f x > y then ( t u n i x ) goto L2 e l s e B goto NextLine
L2 : i f ( y > x ) then A goto NextLine e l s e B goto NextLine
NextLine :
Aufgabe 6.4 (Syntaktischer Zucker: Schleifen)
Zeigen Sie, dass f or-Schleifen mit Registermaschinen simuliert werden können. Hierbei soll sich
L1 :
BODY1:
..
.
BODYn:
L2 :
L3 :
f o r xi do
...
...
od
wie folgt verhalten: Sei der Registerinhalt von xi durch j gegeben. Dann soll der Rumpf der f or-Schleife (hier
gegeben durch die Label BODY1 bis BODYn) genau j-mal ausgeführt werden. Insbesondere ist die Anzahl
der Wiederholungen nicht abhängig von Änderungen des Registerinhaltes von xi . Anschließend wird mit der
Ausführung am Label L3 fortgefahren.
Lösungsvorschlag 6.4
Wir stellen f or-Schleifen wie folgt in Registermaschinen-Code dar. Sei hierbei xk ein bisher nicht genutztes
Register. Der Sprung goto L2 im Rumpf der Schleife (also der Sprung, der die Schleife beendet) wird ersetzt
durch goto DEC. Den Sprung zu FIN könnte man auch direkt mit dem Sprung zu L3 verknüpfen, wir nutzen
ihn aber zur besseren Verständlichkeit.
L1 :
xk = x1 goto CHECK
2/6
CHECK:
BODY1:
..
.
i f ( xk =? 0 ) then goto FIN e l s e goto BODY1
...
BODY2:
DEC:
FIN :
L3 :
...
xk = xk−1 goto CHECK
goto L3
Aufgabe 6.5 (Syntaktischer Zucker: Schleifen die Zweite)
Zeigen Sie, dass while-Schleifen mit Registermaschinen simuliert werden können. Hierbei soll sich
L1 :
BODY1:
..
.
BODYn:
L2 :
while ( xi 6= 0 ) do
...
...
od
wie folgt verhalten: Sei der Registerinhalt von xi durch j gegeben. Dann soll der Rumpf der while-Schleife
(hier gegeben durch die Label BODY1 bis BODYn) so lange ausgeführt werden, bis der Registerinhalt von xi
0 ist. Insbesondere ist die Anzahl der Wiederholungen abhängig von Änderungen des Registerinhaltes von xi .
Anschließend wird mit der Ausführung am Label L3 fortgefahren.
Lösungsvorschlag 6.5
Wir können while-Schleifen nahezu genau so, wie f or-Schleifen in Registermaschinen-Code darstellen: Wir
streichen L1, prüfen in CHECK x1 auf 0 statt xk und streichen DEC. Dementsprechend muss der Sprung nach
DEC durch einen direkten Sprung zu CHECK ersetzt werden.
Aufgabe 6.6 (Syntaktischer Zucker: Funktionsaufrufe)
Aus Programmiersprachen wie SML oder Java kennen Sie die Möglichkeit Prozeduren/Methoden zu definieren,
die sie dann später in weiteren Programmen verwenden können. Diese Möglichkeit möchten wir auch für
Registermaschinen haben. Entwerfen Sie eine Methode um Aufrufe der Form:
Funkionsname ( arg1 , arg2 , . . . , argn )
mit einer Registermaschine zu simulieren.
Lösungsvorschlag 6.6
Sei m das größte genutzte Register im Hauptprogramm und n das größte genutzte Register in der aufgerufenen
Prozedur. Schreibe nun jeweils argi in das Register m + i. Füge danach den Code der Prozedur hinten an, wobei
jedes vorkommen des Registers j durch m + j + 1 ersetzt wird. Namen von Labeln werden konsisten in neue Label
umbenannt. Zum Schluss wird das Ergebnis des Funktionsaufrufs in das gewünschte Zielregister geschrieben.
Aufgabe 6.7 (Bekanntes in neuem Licht)
Ein Stack ist eine Datenstruktur mit folgenden Operationen:
push(S, x): Auf S wird das Element x gelegt.
pull(S): Das oberste Element von S wird entfernt. Ist S leer, so bleibt S unverändert.
top(S): Das oberste Element von S wird zurückgegeben.
isEmpty(S): Gibt 1 zurück, falls S leer ist, und 0 sonst.
Implementieren Sie diese vier Operationen mit Hilfe von Registermaschinen.
Hinweis: Alle Elemente eines Stacks sind natürliche Zahlen. Wir stellen einen Stack mit Hilfe der cantorschen
Paarungsfunktion dar. Sei f die bijketive Funktion, die ein Tupel (a, b) auf eine natürliche Zahl n ∈ N abbildet
(d.h. insbesondere, dass fa−1 und fb−1 existieren, wobei fa−1 (n) = a und fb−1 (n) = b). Durch wiederholtes
Anwenden von f können wir so den gesamten Stack in einer einzigen Zahl speichern. Besitzt der Stack n Elemente
3/6
x1 , . . . , xn , so werden sie wie folgt gespeichert: f (n, f (xn , f (xn−1 , . . . , f (x1 , 0) . . . ))). An erster Stelle steht also
die Größe des Stacks, danach folgen die Elemente. Mit Hilfe von f erhalten wir so eine eindeutige natürliche
Zahl als Kodierung für den Stack.
Lösungsvorschlag 6.7
push(S, x):
L1 :
L2 :
L3 :
L4 :
Fin :
x3
x4
x1
x1
= fa−1 (S) + 1 goto L2
= fb−1 (S) goto L2
= f (x, x4 ) goto L4
= f (x3 , x1 ) goto FIN
pull(S):
CHECK:
L1 :
L2 :
L3 :
L4 :
FIN :
i f ( isEmpty(S)=? 1 ) then goto FIN e l s e goto L1
x2 = fa−1 (S) − 1 goto L2
x1 = fb−1 (S) goto L3
x1 = fb−1 (x1 ) goto L4
x1 = f (x2 , x1 ) goto FIN
top(S):
L1 :
L2 :
FIN :
x2 = fb−1 (S) goto L2
x1 = fa−1 (x2 ) goto FIN
isEmpty(S):
L1 :
TRUE:
FALSE :
FIN :
i f ( fa−1 (S) =? 0 ) then goto TRUE e l s e goto FALSE
x1 = 1 goto FIN
x1 = 0 goto FIN
Aufgabe 6.8 (Und jetzt alles zusammen...)
Schreiben Sie nun eine Registermaschine, die Palindrome erkennt. Sie dürfen hierfür alles benutzen, was sie in
den vorherigen Aufgaben implementiert haben! Das Zeichen des Wortes, das Sie überprüfen sollen, befinden sich
in ASCII-Code (also als Zahl kodiert) auf dem Stack S. Falls es sich beim Wort in S um ein Palindrom handelt,
geben Sie 1 zurück, falls nicht, geben sie 0 zurück. Falls der Stack initial leer ist, divergieren Sie. (Viel Spaß
beim Genießen des synaktischen Zuckers!)
Lösungsvorschlag 6.8
Die Idee ist, den Stack zu kopieren und diese Kopie zu reversieren und dann auf Gleichheit zu prüfen.
EMPTY0:
EMPTY1:
DIVERGE:
COPY_STACK0:
COPY_STACK1:
COPY_STACK2:
COPY_STACK3:
COPY_STACK4:
COPY_STACK5:
COPY_STACK6:
x1 = isEmpty ( S )
i f ( x1 =? 0 ) then goto DIVERGE e l s e goto GOAHEAD
i f ( x1 =? 0 ) then goto CHECK_EMPTY 2 e l s e goto STOP
while ( x1 6= 0 ) do
x2 = top ( S )
pull (S)
push (T, x2 )
push (U, x2 )
x1 = isEmpty ( S )
od
4/6
REVERSE0 :
REVERSE1 :
REVERSE2 :
REVERSE3 :
REVERSE4 :
REVERSE5 :
REVERSE6 :
EQUAL0:
EQUAL1:
EQUAL2:
EQUAL3:
EQUAL4:
EQUAL5:
EQUAL6:
EQUAL7:
EQUAL8:
EQUAL9:
EQUAL10 :
EQUAL11 :
EQUAL12 :
EQUAL12 :
NOTEQUAL:
x1 = isEmpty (T)
while ( x1 6= 0 ) do
x2 = top (T)
p u l l (T)
push (V, x2 )
x1 = isEmpty (T)
od
x1 = stackEmpty (U)
while ( x1 6= 0 ) do
x2 = top (U)
x3 = top (V)
p u l l (U)
p u l l (V)
x4 = x2 − x3
x5 = x3 − x2
i f ( x4 = 0 ) then goto EQUAL9 e l s e goto NOTEQUAL
i f ( x5 = 0 ) then goto EQUAL10 e l s e goto NOTEQUAL
x1 = isEmpty (U)
od
x0 = 1
goto STOP
x0 = 0
STOP:
Aufgabe 6.9 (Zum Knobeln: Programmiersprachen)
In dieser Aufgabe betrachten wir zwei verschiedene Programmiersprachen, die FOR- und die WHILE-Sprache.
Diese sind wie folgt definiert: Beide Sprachen enthalten Variablen x1 , x2 , x3 , . . . und Konstanten 0, 1, 2, . . . . Wir
bezeichnen die Menge der Variablen mit V ar und die der Konstanten mit Kon. Einfache Anweisungen haben
die folgende Form:
(1) xi := xj + xk
(2) xi := xj − xk
(3) xi := c
oder
oder
wobei xi , xj , xk ∈ V ar und c ∈ Kon. Alle diese Anweisungen verhalten sich erwartungesgemäß. Ein FORProgramm ist entweder eine einfache Anweisung oder eine Anweisung der folgenden Form:
(4) for xi do P1 od
(5) P1 ; P2
oder
wobei xi ∈ V ar und P1 und P2 FOR-Programme darstellen. (5) stellt die Konkatenation zweier Programme dar.
Analog können WHILE-Programme definiert werden. Jedoch enthalten sie statt f or-Schleifen while-Schleifen
der Form while (xi 6= 0) do P1 od und es können nur WHILE-Programme konkateniert werden.
1.
2.
3.
4.
5.
Entwerfen Sie ein FOR-Programm, dass die Funktion grtr aus Aufgabe 6.2 berechnet.
Entwerfen Sie ein WHILE-Programm, dass die Funktion div3 aus Aufgabe 6.2 berechnet.
Zeigen oder widerlegen Sie: Jedes FOR-Programm kann durch ein WHILE-Programm simuliert werden.
Zeigen oder widerlegen Sie: Jedes WHILE-Programm kann durch ein FOR-Programm simuliert werden.
Diskutieren Sie: In welchem Verhältnis stehen Registermaschinen, FOR- und WHILE-Programme?
Lösungsvorschlag 6.9
1. Wir nehmen an, dass x in Variable x1 und y in Variable x2 steht.
x3 = x1
x1 = 0
x2 = x3 − x2 // Berechne x − y
f o r ( x2 ) do// F a l l s x−y > 0 i s t , dann wird x1 a u f 1 g e s e t z t
x1 = 1 od
2. noch keine Beispiellösung
5/6
3. Es brauchen nur for-Schleifen simuliert zu werden, da alles andere identisch ist. Eine for-Schleife kann
durch
xj = 0 // xj i s t e i n e neue V a r i a b l e
xj = xi + xj
xk = 1 // xk i s t e i n e neue V a r i a b l e
while ( xj 6= 0 ) do
P1
xj = xj − xk od
simuliert werden.
4. Nicht jedes While Programm, kann durch ein For-programm simuliert werden, da es WHILE-Programme
gibt, die partielle Funktionen berechnen. Das While Programm
while ( x1 6= 0 ) do
x1 = 1 od
berechnet zum Beispiel, eine Funktion, die nur auf dem Argument 0 definiert ist. Da For-Programme immer
terminieren, kann dieses While-Programm nicht von einem For-Programm simuliert werden.
5. While Programme und Registermaschinen sind gleichmächitig. For Programme hingegen können weniger
berechnen.
6/6

Download Report