Alternativer Lösungsvorschlag

Question

Würde die TM wenn ich erst invertiere und dann eine 1 addiere so aussehen oder habe ich da wichtige Zustände vergessen?

          0          1          *

s0    s0,1,R  s0,0,R  s1,*,L

s1    se,1,R  s1,0,L  se,*,R

se

Vielen Dank!

 

Answer 1

Ich denke deine Zustandstabelle ist fast richtig.

Du hast allerdings den Fall vergessen, wenn zum Beispiel das Eingabewort nur aus 0 besteht. also nehmen wir an die Bandinschrift ist "0000". durch das invertieren erhalten wir natürlich 1111. Wenn man nun aber noch die 1 addiert erhält man 10000, also ein Zeichen mehr auf dem Band. Das heißt du musst ganz links noch eine 1 anfügen. Also (s1, *) -> (se, 1, N)

Außerdem sollen wir ja am Ende über dem linkesten Zeichen stehen bleiben, das ist in deiner Lösung nicht berücksichtigt.

Grüße, Theresa (Tutorin)