Binärer Rückwärtszähler mit < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:48 Do 30.05.2013 | | Autor: | bandchef |
| Aufgabe | Konstruieren sie einen binären Rückwärtszähler mit Hilfe einer deterministischen Turing-Maschine.
Bei Eingabe $x = [mm] x_1 x_2 [/mm] ... [mm] x_n$ [/mm] mit [mm] $x_i \in \{0,1\} [/mm] soll nacheinander x-1, x-2, x-3, ..., 0 auf dem Band ausgegeben werden (an "gleicher Position", also nicht hintereinander!). |
Hi Leute!
Bevor ich mit dem beschreiben der DTM anfangen kann muss ich das ja erstmal auf dem Papier "durchspielen", daher brauch ich eure Hilfe, denn:
Ich weiß nicht welcher Algorithmus hinter so einem Rückwärtszähler liegt, also quasi in welcher Art Reihenfolge ich die jeweils letzten Zeichen löschen muss!
Kann mir jemand helfen?
|
|
| |
|
Hallo bandchef,
> Ich weiß nicht welcher Algorithmus hinter so einem
> Rückwärtszähler liegt, also quasi in welcher Art
> Reihenfolge ich die jeweils letzten Zeichen löschen muss!
>
> Kann mir jemand helfen?
Es ist doch eine "simple" Subtraktion.
![[]](/images/popup.gif) Subtraktion von Binärzahlen
Gruß
Anna
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:45 Do 30.05.2013 | | Autor: | bandchef |
Ehrlich gesagt ist mir diese Vorgehensweise, wie sie hier erklärt wird, suspekt! Ich hab gelernt, dass man binäre Zahlen nur mit Zweierkomplement subtrahieren darf!
| 1: |
| | 2: | 1000
| | 3: | - 0110
| | 4: | 1
| | 5: | ------
| | 6: | 1010
|
0. Stelle: 0-0=0
1. Stelle: 0-1=1 und an nächste Stelle (2. Stelle) den Übertrag
2. Stelle 0-1-1 = 0
3. Stelle: 1 (einfach runterziehen)
Ergebnis ist niemals 2 sondern 10!
Wenn ich das ganze nun aber mit Zweierkomplement berechne:
| 1: |
| | 2: | 1000
| | 3: | + 1010
| | 4: | 1
| | 5: | ------
| | 6: | 0010
|
... komm ich auf's richtige Ergebniss. Übertrag wird einfach abgeschnitten und schon passt das! Für meine Berechnung, den binären Rückwärtszähler, müsste ich quasi eine Zahl mit so vielen 1en subtrahieren, die mit der Anzahl der rückwärts zu zählenden Zahl übereinstimmt.
Hier schon mal ein kleiner Entwurf: http://s14.directupload.net/file/d/3272/bsy67gcx_jpg.htm Ich hab hier nun wieder das Problem mit dem finalen Zustand. Wenn die Zahl 111 bei 000 angekommen ist, hält die TM nicht. Kannst du mir drauf helfen wo und wie ich den finalen Zustanden anbauen muss? Ich hoffe du kannst mir gezielter nachhelfen 
NOCHMALIGES EDIT:
Ich glaub jetzt hab ich's!!!!
DTM-Bild: http://s7.directupload.net/file/d/3272/yb44o9b3_jpg.htm
Wär nett wenn die DTM jemand überprüfen könnte! Danke!
|
|
|
| |
|
Hallo bandchef,
> erklärt wird, suspekt! Ich hab gelernt, dass man binäre
> Zahlen nur mit Zweierkomplement subtrahieren darf!
Da wir hier ja immer nur "minus 1" rechnen, ist der Subtrahend nie größer als der Minuend und man kann es auch ohne Zweierkomplement machen.
> NOCHMALIGES EDIT:
> Ich glaub jetzt hab ich's!!!!
Du bist schon auf den richtigen Weg, ja.
> DTM-Bild:
> http://s7.directupload.net/file/d/3272/yb44o9b3_jpg.htm
>
> Wär nett wenn die DTM jemand überprüfen könnte! Danke!
Wie machst Du das eigentlich, wenn Du eine TM entwickelt hast, spielst Du das dann auch mal für ein paar Testeingaben selbst durch?
Also ich komme bei #100# auf 111 mit Deiner TM.
Gruß
Anna
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:22 Fr 31.05.2013 | | Autor: | bandchef |
Ich hab es für das Wort 11 ausprobiert und da hat's funktioniert!
Jetzt schreib ich in q5 bei einer gelesenen 0 eine 1 und in q5 bei einer gelesenen 1 eine 0. Jetzt funktioniert das ganze aber wieder nicht.
Kannst du mir nicht sagen, was da noch immer schief läuft? Ich komm da nicht drauf...
|
|
|
| |
|
Hallo bandchef,
> Ich hab es für das Wort 11 ausprobiert und da hat's
> funktioniert!
Ich würde prinzipiell das für mehrere Möglichkeiten immer austesten an Deiner Stellen, also für alle Eingabezeichen.
> Jetzt schreib ich in q5 bei einer gelesenen 0 eine 1 und in
> q5 bei einer gelesenen 1 eine 0. Jetzt funktioniert das
> ganze aber wieder nicht.
>
> Kannst du mir nicht sagen, was da noch immer schief läuft?
> Ich komm da nicht drauf...
Wie ist das denn jetzt, wie ist Dein "Algorithmus" im Kopf bzgl. der Subtraktion von 1. Also wann ist was zu ändern? Du hast ja schon richtig angefangen, von wegen, wenn die letzte Zahl eine 1 ist, dann wird das eine Null. Wie ist das weitere Schema, wie hast Du Dir das gedacht?
Gruß
Anna
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:38 Fr 31.05.2013 | | Autor: | bandchef |
q2 entscheidet ob kein übertrag und q3 entscheidet ob übertrag. wenn man in q3 bzw. q5 bei linkem # ist, wird immer in q6 überprüft ob nur mehr 0en verfügbar sind, wenn ja dann q7 und halten.
soweit ist das mein algorithmus.
Wenn ich 100 rückwärtszählen lasse und bei 001 angekommen wirds falsch. das Problem hier ist dann q5, weil dieser zustand aus der rechtesten 0 eine 1 machen will. ich kann aber auch nicht einfach in q5 das zu schreiben zu zeichen von 1 zu 0 wechseln weil's dann an anderer Stelle wieder hakt.
Genau hier ist nun mein Problem! ich blicke nun einfahc nicht mehr was ich ändern muss!
|
|
|
| |
|
Hallo bandchef,
ich wollte eigentlich unabhängig von der TM wissen, wie Dein Algorithmus ist? Also wie ist das bei der binären Subtraktion mit 1, wann ändert sich da was?
>Genau hier ist nun mein Problem! ich blicke nun einfahc nicht mehr was ich ändern muss!
Wie wäre es mit noch ein paar Zuständen mehr - damit Du weißt, wann der Übertrag "beendet" ist und danach halt die Zeichen nicht mehr verändert werden müssen? Das vielleicht noch als weiteren Tipp.
Gruß
Anna
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:26 Sa 01.06.2013 | | Autor: | bandchef |
Der allgemeine Algorithmus:
Ich multipliziere zum subtrahieren immer das zweierkomplement als 1en. wenn nun an letzter Stelle 0 kommt gibts keinen übertrag wenn eine 1 kommt, dann gibts einen übertrag und ich muss jeweils zwei verschiedene wege einschlagen und je nachdem das bit auf 0 oder 1 setzen. dann kommt die nächste stelle. das gleich wieder. usw usf...
Wie gesagt, das Problem entsteht in q5 wenn die TM auf der linkesten 0 im Wort 001 steht. Er liest dann eine 0 und kippt diese zu 1.
|
|
|
| |
|
Hallo bandchef,
> Ich multipliziere zum subtrahieren immer das
man muss ja wie gesagt gar nicht den Weg mit dem Zweierkomplement gehen. Aber gut, kommt ja aufs Gleiche raus.
> zweierkomplement als 1en. wenn nun an letzter Stelle 0
> kommt gibts keinen übertrag wenn eine 1 kommt, dann gibts
> einen übertrag und ich muss jeweils zwei verschiedene wege
> einschlagen und je nachdem das bit auf 0 oder 1 setzen.
> dann kommt die nächste stelle. das gleich wieder. usw
> usf...
>
> Wie gesagt, das Problem entsteht in q5 wenn die TM auf der
> linkesten 0 im Wort 001 steht. Er liest dann eine 0 und
> kippt diese zu 1.
Wo liegt das Problem, dass Du noch Zustände einbaust für den Fall, wo eben dann nichts mehr weiter geändert werden muss (also 0 bleibt 0 und 1 bleibt 1)?
Gruß
Anna
|
|
|
|
