Turingmaschine Binär in Unär

Wissenschaft Informatik
#1

Hallo leute,
stehe gerade vor einer kniffligen aufgabe und hab gedacht man kann mir hier weiterhelfen.
zu meiner frage: ich brauch eine turingmaschine die mir aus einer binär zahl z.b. 110 (5) eine unäre zahl 11111 erstellt. und das in jflap. habe natürlich schon rumgetüffelt aber verzweifle langsam daran… sicher steckt ein ganz einfacher trick dahinter aber ich komme nicht drauf und google kann auch nicht helfen. meine idee war folgende: springe erst ganz nach rechts. dann überprüfe die erste ziffer wenn eine 1 da steht dann hänge eine 1 rechts von der 110 an dann springe weiter auf die zweite stelle wenn da eine 1 steht dann hänge zu der bestehenden 1 noch zwei weitere 1en an. für dritte stelle vier 1en usw. am ende lösche die 110 (oder währenddessen je nachdem) aber an der verwirklichung meiner idee scheiterts!

habt ihr vielleicht noch anregungen dazu?

#2

Hallo slowmo,

ein möglicher Algorithmus ist folgender:

PRE: Eingabe >= 1, keine führenden Nullen

(1) Lösche das höchstwertige Bit der Eingabe, schreibe ‚|‘ als initiale Ausgabezeichenfolge
(2) Solange Eingabe nicht vollständig gelöscht:
(2.1) Ist das das höchstwertige Bit der verbliebenen Eingabe ‚0‘, dann lösche die ‚0‘ undverdopple die bisher vorhandene Ausgabezeichenfolge
(2.2) Anderenfalls (MSB ist ‚1‘) lösche die ‚1‘, verdopple die bisher vorhandene Ausgabezeichenfolge und hänge zusätzlich ein ‚|‘ an.
(3) fertig, wenn Eingabe vollständig gelöscht.

Das jeweilige Verdoppeln der Ausgabezeichenfolge ist auch nochmal eine nette Knobelaufgabe, mit einer 1-Band TM noch mehr als mit einer n-Band TM.

Gruß,
KHK … mehr auf http://w-w-w.ms/a5eexs

#3

Mein Ansatz:

PRE:
  - Das Alphabet besteht nur aus 0, 1
  - der Startpunkt ist die 1-er Stelle                             
  - die maximale Anzahl signifikanter Stellen ist festgelegt.
 
Die Idee: rechts von der 1-er Stelle wird eine 1 als Grenzmarkierung gesetzt (Status 2).
Dann wieder auf den Startpunkt (Status 3).
Dann nach links mit jeweils neuem Status:
   - bei der binär-Ziffer 1 (diese auf 0 setzen) solange nach rechts bis 0,
     danach soviele 1 wie dem Stellenwert der binär-Ziffer entspricht (erkennbar am Status)     
   - bei der binär-Ziffer 0 nach links bis zur nächsten 1 oder
     bis zur maximalen Stellenzahl - In diesem Fall nach rechts alle 0 überspringen bis zur 1,
     diese auf 0 setzen - fertig

Das Statusdiagramm: http://gyazo.com/bb95a38c73fd8a9ecdc36a0a4350b231

bis auf eventuelle Fehler müsste das so gehen. Ich hoffe das hilft ein wenig.

Gruß, Max.

#4

Hallo zusammen,
danke euch beiden war beides sehr hilfreich habe mich aber dann für den algorithmus von KHK entschieden. die anzahl der 1en wird nun unär korrekt angegeben nur weiß ich nicht so recht wie ich die 0er weg bekomme. wenn ich in jflap dafür ein leeres zeichen eingebe werden alle 1en hinter der 0 abgeschnitten. ich lade mal den code hoch für jflap: https://www.dropbox.com/s/amkojsj4oqqp2hy/Aufgabe5.jffund noch einen screenshot vom statechart: https://www.dropbox.com/s/rsivn1wu9183i2k/SS-StateCh…danke nochmal den richtigen algorithmus zu finden ist immer das schwierige bei solchen sachen aber naja hoffentlich wird das noch :smiley:

Gruß Slowmo