entscheidbarkeit turing-maschine konstruieren?
Sei L eine entscheidbare Sprache. Zeigen Sie dass die Sprache L′ auch entscheidbar ist, wobei
L′ = {w | w · w^r ∈ L},
und w · w^r ist die Konkatenierung des Wortes w mit seiner Umkehrung.
kann mir hierbei jemand helfen?
1 Antwort
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Informatik
Was wäre denn, wenn Du die TM selbst invertierst und mit der ursprünglichen 'verschmilzt'?
Also Endzustand der Original-TM ist zugleich Startzustand der invertierten TM. Der ursprüngliche Startzustand akzeptiert dann bei der invertierten TM. Die Transitionen werden umgekehrt ebenso wie die Bandrichtung.
Überleg mal, ob so eine Konstruktion machbar ist.
(Ist nru eien spontane Idee, vielleicht geht es auch anders)
P.S.: Die Bandrichtung sollte natürlich nicht invertiert werden, da habe ich zu schnell geschossen....