 Turing Maschine String Vergleich |
Theo_Info_12
unregistriert
 |
|
| 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! 
|
|
30.11.2017 10:03 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo Theo_Info_12,
Vorab: Theoretische Inf ist bei mir auch eine weile her. Bitte also alle Anahmen und Angaben kritisch hinterfragen.
zu 1) ich würde die Strings nicht von der Länge her vergleichen. Das wäre ein unnützer Schritt zu viel. Wir machen uns für jedes Zeichen des Eingabealphabets einen Zustand. Wir lesen das erste Zeichen des ersten Bandes und ersetze es direkt durch das leere Feld. Danach gehen wir bis zum ersten Zeichen nach den Trennzeichen '#' (mehrzahl ist hier gewollt). Wir erwarten da wieder das gleiche Zeichen wie beim ersten Wort. Wenn es das gleiche Zeichen ist, ersetzen wir es durch das Trennzeichen '#' und gehen zurück bis an den Anfang des ersten Wortes. Das wiederholen wir so oft, bis wir ungleiche Zeichen oder das Ende beider Worte erreicht haben. Das dürfte durch das Hin und Her quadratische Laufzeit ergeben.
zu 2)
Gleiche Eingabe wie in 1). Eingabe steht auf dem ersten Band. Wir gehen bis zum Zweiten Wort und Kopieren es auf das Zweite Band und laufen wieder Zurück bis zum Anfang des ersten Wortes. Laufzeit dürfte linear sein.
Dann Vergleichen wir Gleichzeitig Band 1 und 2. Laufzeit dürfte wiederum linear sein.
Insgesamt kommen wir also auf lineare Laufzeit.
Betrachtung der ersten TM: relativ sparsam, jedoch ungünstiges Laufzeitverhalten
Betrachtung der zweiten TM: Viele Zustsände (Es werden extra Zustände für das Kopieren gebraucht) + weiteres Band, jedoch günstiges Lauzeitverhalten
Da unabhängig von der Länge der Eingabewörter die Anzahl an zusätzlichen Zuständen gleich bleibt, die Laufzeit jedoch erheblich besser ist, gewinnt die zweite TM.
Besten Gruß
Karlito
|
|
|
01.12.2017 17:15 |
|
|
Theo_Info_12
unregistriert
|
|
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
|
|
|
03.12.2017 14:55 |
|
|
|
