Seien x = (x_n x_n-1 … x_2 x_1 x_0)bin und y (y analog zu x) jeweils Binärzahlen, d.h. x_i in {0,1}.
Geben Sie einen deterministischen endlichen Automaten an, der für beliebige n genau die Eingabe w = x_n y_n x_n-1 y_n-1 … x_1 y_1 x_0 y_0 mit |x-y| <= 2 akzeptiert.
Hinweis: die Darstellung von x und y kann fphrende Nullen enthalten.
Ideen: Momentan keine.
Das scheint bei deinen Beiträgen schon fast System zu haben…
Die Grundbegriffe von DEA kennst du aber, oder?
Kannst du bitte mal ein Bildschirmfoto/Bildschirmausschnitt von der Aufgabenstellung machen? So mag ich, und andere viell. auch, das gar nicht lesen.
das stimmt ja gar nicht, die letzte Frage konnte ich z.b. selbst lösen. Ja ich weiss wie DEAs funktionieren.
Wie dem auch sei - zumindest hat dieser Satz von dir bei mir Erinnerungen an vorige Fragen hervorgerufen.
Das ist schonmal ein guter Anfang.
Folgende Herangehensweise ist für mich die offensichtlichste (mag für andere anders aussehen):
Edit: Ich habe das gerade mal testweise aufgeschrieben: mit 10 Zuständen kommt man aus, um diesen Ansatz umzusetzen. Von den 10 Zuständen sind 4 akzeptierend.
so wäre meiner Meinung nach bisher gleich ansonsten muss dass Ergebnis ja irgentwie 0, 1, 2, -1, -2 im Dezimalsystem sein aber ich weiss nicht wie die binärzahlen aussehen müssen damit das erreicht wird. Und woher weiss ich wann ich die letzten zwei bits lese ( die letzten zwei bits von einem Wort oder von beiden gemischt?=
ah ok wenn das Ergebnis zwei sein muss ist die letzte binärziffer gleich und die vorletzte verschieden
Das sieht schonmal ganz gut aus. Zur Sicherheit: welches davon ist der Startzustand? Ist von diesen Zuständen bereits einer akzeptierend?
Das ist soweit auch schon die richtige Richtung. Damit die Differenz im Intervall von -2 und 2 liegt, müssen alle bis auf die letzten zwei Bits gleich sein, sonst wird die Differenz auf jeden Fall zu groß.
Nun musst du noch herausfinden, welche Bitkombinationen akzeptiert werden sollen und welche nicht. Dazu schreibst du am besten alle 16 Kombinationsmöglichkeiten auf und markierst die, die gültig sind, also bei denen die Differenz im gewünschten Intervall liegt.
Dabei sollte dir dann etwas auffallen.
mich verwirren die negativen zahlen ehrlich gesagt muss man dann irgentwas mit zweierkomplement machen?
wenn das Ergebnis 1 sein soll müssen die zahlen ja gleich sein bis auf das letzte bit
aber z.b. 2 - 4 = -2 |-2| = 2 0010 - 0100 die unterscheiden sich ja auch im drittletzten bit?!?
Negative Zahlen im eigentlichen Sinne gibt es dort nicht. Der DEA rechnet ja nicht, sondern akzeptiert nur Worte, die die gestellten Bedingungen erfüllen.
Du hast Recht, mein Ansatz würde wohl nicht korrekt funktionieren. Da muss ich jetzt auch nochmal überlegen 
Im Endeffekt deuten die Hinweise auf die Richtung, die ich vorgeschlagen hatte. Nur, dass ich nicht berücksichtigt hatte, dass die Zahlen sich nahezu vollständig unterscheiden, und trotzdem dicht beieinander liegen können (letzter Hinweis).
Du bist auf meine Fragen zu Start- und akzeptierenden Zuständen bei deinem Gleichheitsautomaten noch nicht eingegangen.
der startzustand ist links oben und der müsste auch schon akzeptierend sein
mhh ka wenn das erste bit verschieden ist, dann dürfen alle bits bis auf das letzte invertiert sein?!?
Passt.
Nein, versuch nochmal systematisch an das Problem heranzugehen. Stück für Stück.
x soll größer als y sein. D. h., dass x und y von der Bitfolge her gleich sind, y dann aber irgendwann eine 0 an der Stelle stehen hat, wo x noch eine 1 hat. Wie darf die Bitfolge nun weitergehen, damit x maximal genau 2 größer ist als y?
nach dieser stelle alles invertieren bis auf die letzte stelle?
Hm, ja, ich hab das (diesesmal) gelesen. Zuerst hab ich mich gefragt, wie die zwei Binärzahlen getrennt sind, dann hab ich n gesehen, dann hab ich mich gefragt, welchen Wertebereich n denn nun hat, „für beliebige n“, ist an der Stelle etwas ungenau, zählt ihr 0 zu den natürlichen Zahlen? Nachdem ich dann die Aufgabenstellung verstanden hab, immer eine Ziffer der ersten, dann der zweiten Zahl usw.
Du musst von xi yi abziehen, da gibt’s ja nur 4 Fälle. Ich muss das aufmalen ( @cmrudolph hat recht mit 10 Zuständen):
Accept: 0000 -- Pass
Accept: 0001 -- Pass
Accept: 0010 -- Pass
Accept: 0011 -- Pass
Accept: 0100 -- Pass
Accept: 0101 -- Fail
Accept: 0110 -- Pass
Accept: 0111 -- Pass
Accept: 1000 -- Pass
Accept: 1001 -- Pass
Accept: 1010 -- Fail
Accept: 1011 -- Pass
Accept: 1100 -- Pass
Accept: 1101 -- Pass
Accept: 1111 -- Pass
Reject: [Empty String] -- Fail
Bitte mal nicht hauen, wenn ich das mal nicht so gut layouted hab. Das wäre nett. 
Quelle: http://automatonsimulator.com/
Spielstand (damit ihr euch nicht Mühe geben müsst):
{"type":"DFA","dfa":{"transitions":{"start":{"0":"s0","1":"s1"},"s0":{"0":"start","1":"s3"},"s1":{"0":"s2","1":"start"},"s3":{"0":"s4","1":"s5"},"s4":{"0":"s3","1":"s6"},"s5":{"0":"start","1":"s3"},"s2":{"0":"s7","1":"s8"},"s7":{"0":"s2","1":"start"},"s8":{"0":"s6","1":"s2"},"s6":{"0":"s6","1":"s6"}},"startState":"start","acceptStates":["start","s3","s2"]},"states":{"start":{"isAccept":true},"s0":{"top":197,"left":315},"s1":{"top":510.0000305175781,"left":315},"s3":{"isAccept":true,"top":185,"left":587},"s2":{"isAccept":true,"top":507.0000305175781,"left":591},"s4":{"top":125,"left":837},"s5":{"top":258,"left":834},"s6":{"top":347,"left":1212},"s7":{"top":421,"left":799},"s8":{"top":532.0000305175781,"left":820}},"transitions":[{"stateA":"start","label":"0","stateB":"s0"},{"stateA":"start","label":"1","stateB":"s1"},{"stateA":"s0","label":"0","stateB":"start"},{"stateA":"s0","label":"1","stateB":"s3"},{"stateA":"s1","label":"0","stateB":"s2"},{"stateA":"s1","label":"1","stateB":"start"},{"stateA":"s3","label":"0","stateB":"s4"},{"stateA":"s3","label":"1","stateB":"s5"},{"stateA":"s4","label":"0","stateB":"s3"},{"stateA":"s4","label":"1","stateB":"s6"},{"stateA":"s5","label":"0","stateB":"start"},{"stateA":"s5","label":"1","stateB":"s3"},{"stateA":"s2","label":"0","stateB":"s7"},{"stateA":"s2","label":"1","stateB":"s8"},{"stateA":"s7","label":"0","stateB":"s2"},{"stateA":"s7","label":"1","stateB":"start"},{"stateA":"s8","label":"0","stateB":"s6"},{"stateA":"s8","label":"1","stateB":"s2"},{"stateA":"s6","label":"0","stateB":"s6"},{"stateA":"s6","label":"1","stateB":"s6"}],"bulkTests":{"accept":"0000\n0001\n0010\n0011\n0100\n0110\n0111\n1000\n1001\n1011\n1100\n1101\n1111","reject":"0101\n1010\n101010"}}
Fragen an @bisaflor :
Hint:
Bei Bulk Testing schreibt man das nicht zu Akzeptierende nicht zu Accept. 
(Hab ich wohl verstanden)