Seite 1 von 1

Blatt 12

BeitragVerfasst: 23.01.2009 15:53
von mabl
Sagt mal, habt ihr eine schöne Möglichkeit gefunden, diese beiden Wörter bei der 12.1 b) zu vergleichen? Ich scheiter etwas daran, das die Wörter beide beliebige Längen haben können. Daher muss ich sie beide zuerst richtig formatiert in einen anderen Bandbereich kopieren - und das wird eine RIESEN Maschine... Wenn ich fertig bin stell ichs mal online - aber ich wäre dankbar wenn jemand einen beseren Algo hat, der das Kopieren nicht nötig hat...

Re: Blatt 12

BeitragVerfasst: 23.01.2009 17:04
von mabl
Also ich hänge mal meine Lösung für die 12.1b) an. Ich denke aber, sie ist viel zu kompliziert... ich kam aber einfach nicht drauf, wie ich die größe von zwei Wörtern _variabler_ Länge vergleichen kann, ohne sie zuerst geordnet in einen neuen Speicherbereich zu kopieren. Dafür ist das aktuelle Vergleichen ab Zustand q_20 geradezu trivial einfach, wenn es denn mal geordnet ist :mrgreen:

EDIT: Die 12.2.a) ist allerdings wieder einfach.. siehe Anhang
EDIT2: Habe eine Idee für die 12.1b) - ich probier das morgen mal aus - sorry für die Umstände..

Re: Blatt 12

BeitragVerfasst: 24.01.2009 11:46
von mabl
Also hier mein Vorschlag für die 12.1.b) - Achtung, ich habe bei dem Graphen das Ersetzen, der führenden 1 bei w1 und w2 in Schritt III vergessen einzubauen. Der Algorithmus sollte aber klar sein.

Der Vergleich funktioniert wie folgt, nehmen wir das Beispiel

a0101b0111

Schritt I
aa101bb111
Ersetze alle führenden Nullen durch entsprechende "a" oder "b".

Schritt II
a)
aa101bb111BBB
Schreibe so viele "B"s wie nach den "b" Trennzeichen vorhanden sind ans ende des Wortes

b)
aa101bb111XXX
Schreibe so viel Zeichen ans Ende der Daten, wie nach "a" kodiert sind. Dabei werden alle schon vorhanden "B"s durch "X"s ersetzt. Ist kein Zeichen mehr vorhanden, was überschrieben werden soll, so ist w_1 größer als w_2

Schritt III
Wenn das letzte Zeichen ein X ist, so war unentschieden, die führende 1 wird zu einem a oder b. Die angehängten Zeichen werden wirder gelöscht. -> Gehe zu Schritt 1
Wenn das letzte Zeichen ein b war, so waren die Zahlen gleich groß.


Die Bearbeitung des Beispielsatzes wird also so Abgearbeitet:

a0101b0111
aa101bb111
aa101bb111BBB
aa101bb111XXX
aaa01bbb11
aaaa1bbb11
aaaa1bbb11XB

-> Letztes Zeichen ist ein B -> w_2 ist größer

Re: Blatt 12

BeitragVerfasst: 24.01.2009 14:48
von M.A.
Das is ja'n Riesengraph! Herrje...

Damit du hier nicht so alleine schreibst, verkünde ich, dass die Maschine aus der 12.2b) das Eingabewort spiegelt, es quasi nimmt, umdreht und hinter das Ursprungswort hängt. (Beispiele:ab ---> abba, bab ---> babbab, aaab ---> aaabbaaa)

Re: Blatt 12

BeitragVerfasst: 27.01.2009 19:09
von mfs
M.A. hat geschrieben:Damit du hier nicht so alleine schreibst, verkünde ich, dass die Maschine aus der 12.2b) das Eingabewort spiegelt, es quasi nimmt, umdreht und hinter das Ursprungswort hängt. (Beispiele:ab ---> abba, bab ---> babbab, aaab ---> aaabbaaa)


Das kann ich bestätigen. Dieses JAVA-Applet ist bei der Verifizierung hilfreich: http://ironphoenix.org/tril/tm/

Einfach folgenden Code eingeben, Install Program drücken, Initial Characters on tape eingeben (das Eingabewort) und Start drücken.

Code: Alles auswählen
1,_,2,_,<
1,a,1,c,>
1,b,1,d,>
1,c,1,c,>
1,d,1,d,>
2,_,H,_
2,a,2,a,<
2,b,2,b,<
2,c,3,a,>
2,d,4,b,>
3,_,2,a,<
3,a,3,a,>
3,b,3,b,>
3,c,3,c,>
3,d,3,d,>
4,_,2,b,<
4,a,4,a,>
4,b,4,b,>
4,c,4,c,>
4,d,4,d,>


MfG,
mfs.

Re: Blatt 12

BeitragVerfasst: 27.01.2009 21:24
von mfs
Hi,

mein Ergebnis bei der 12.1b) sieht so aus (als Programmcode für das Java-Applet aus dem Post vorher), die Endzustände heißen H mit Ausgabe E (gleich), G (größer), L (kleiner).

Code: Alles auswählen
1,1,14,1,>
1,0,1,a,>
1,a,1,a,>
1,b,15,b,>
14,1,14,1,>
14,0,14,0,>
14,b,15,b,>
15,1,16,1,<
15,0,15,b,>
15,b,15,b,>
15,_,18,_,<
16,1,2,1
16,0,2,0
16,b,16,b,<
16,a,H,L
2,1,3,0
2,0,2,1,<
2,a,2,a,>
2,b,11,b
3,_,4,_,<
3,1,3,1,>
3,0,3,0,>
3,a,3,a,>
3,b,3,b,>
4,1,5,0
4,0,4,1,<
5,1,5,1,<
5,0,5,0,<
5,a,6,a,>
5,b,5,b,<
6,1,7,1
6,0,6,a,>
6,a,6,a,>
6,b,8,b
7,1,7,1,>
7,0,7,0,>
7,b,8,b,>
8,1,9,1
8,0,8,b,>
8,b,8,b,>
8,_,9,_,<
9,1,9,1,<
9,0,9,0,<
9,a,10,a
9,b,9,b,<
10,1,12,1
10,0,12,0
10,a,10,a,>
10,b,11,b
11,_,H,E
11,1,H,L
11,b,11,b,>
12,1,12,1,>
12,0,12,0,>
12,b,13,b,>
13,_,H,G
13,1,17,1,<
13,0,17,0,<
13,b,13,b,>
17,1,17,1,<
17,0,17,0,<
17,a,1,a,>
17,b,17,b,<
18,1,H,G
18,0,H,G
18,a,H,E
18,b,18,b,<


Bis jetzt habe ich noch kein Beispiel finden können, bei dem es nicht stimmt...

MfG,
mfs.