Blatt 12

Blatt 12

Beitragvon mabl » 23.01.2009 15:53

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...
Benutzeravatar
mabl
Site Admin
 
Beiträge: 741
Registriert: 25.10.2008 11:28
Wohnort: Ettlingen, Karlsruhe

Re: Blatt 12

Beitragvon mabl » 23.01.2009 17:04

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..
Dateianhänge
info12.PDF
12.1.b) - Richtig aber definitiv zu lang - Vergleiche meine Post weiter untern.
(1.64 MiB) 328-mal heruntergeladen
122a.png
12.2.a)
(97.57 KiB) 64-mal heruntergeladen
Benutzeravatar
mabl
Site Admin
 
Beiträge: 741
Registriert: 25.10.2008 11:28
Wohnort: Ettlingen, Karlsruhe

Re: Blatt 12

Beitragvon mabl » 24.01.2009 11:46

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
Dateianhänge
121png.png
(3.7 MiB) 61-mal heruntergeladen
Benutzeravatar
mabl
Site Admin
 
Beiträge: 741
Registriert: 25.10.2008 11:28
Wohnort: Ettlingen, Karlsruhe

Re: Blatt 12

Beitragvon M.A. » 24.01.2009 14:48

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)
Bild
Benutzeravatar
M.A.
 
Beiträge: 366
Registriert: 25.10.2008 16:37

Re: Blatt 12

Beitragvon mfs » 27.01.2009 19:09

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.
Benutzeravatar
mfs
 
Beiträge: 111
Registriert: 31.10.2008 15:16

Re: Blatt 12

Beitragvon mfs » 27.01.2009 21:24

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.
Benutzeravatar
mfs
 
Beiträge: 111
Registriert: 31.10.2008 15:16


Zurück zu Friedhof GbI

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast

cron