Geschrieben von Theo_Info_12 am 30.11.2017 um 10:03:
Turing Maschine String Vergleich
Hallo,
Ich habe in einer Übung zur Theoretischen Informatik gesehen, dass eine TM gebaut werden soll, die zwei Strings vergleicht. Jetzt gibt es hier ja verschiedene Ansätze. (Ich fand die Übung interessant und beschäftige mich gerne damit, Theo ist bei mir schon etwas her...)
1.) Eine Ein-Band TM:
Da stehen dann zwei Binärziffern, welche durch sagen wir mal das Symbol # getrennt sind. Ich würde jetzt die Strings zunächst mit ihrer Länge vergleichen. Dann würde ich konkret durch die beiden Wörter gehen und von links nach rechts über # vergleichen. Ich habe nur das Gefühl, dass das dann eine recht große und aufwändige Maschine wird, ist das so?
2.) Mehr-Band TM:
Ich habe zwei Bänder, wo die Zahle drauf stehen, ich nehme von Band 1 Bsp die 1 oder 0 entgegen und mache das gleiche für Band 2 natürlich parallel ungefähr so, 11 -> 11,11,RR
also lese 1 und 1 schreibe 1 und 1 und gehe nach rechts oder Verknüpft mit dem 0 Fall. das führt dann zu einem akzeptierenden Zustand.
Jetzt ist die Frage, was ist der bessere Ansatz für sowas? Meine erste Idee sollte glaube ich funktionieren, nur wenn man das auf einer 1-Band Maschine macht, wird der Automat glaube ich extrem groß?
Ich würde mich sehr freuen, wenn hier jemand seine Einschätzung abgeben könnte?
Danke!
Geschrieben von Theo_Info_12 am 03.12.2017 um 14:55:
Danke für deine Antwort!
Ja perfekt dann habe ich ja soweit schon richtig überlegt, auch toll, dass man die Länge dann garnicht vergleichen muss
Danke