Zeigen Sie, dass die folgende Sprache in Polynomialzeit entscheidbar ist: L = {w ∈{0, 1}∗| w ist ein Palindrom }.

Question

Aufgabe:

Zeigen Sie, dass die folgende Sprache in Polynomialzeit entscheidbar ist: L = {w ∈{0, 1}∗| w ist ein Palindrom }. Skizzieren Sie dazu eine deterministische 1-Band TuringMaschine ML, welche L entscheidet und begründen Sie die Laufzeit von ML.

Problem/Ansatz:

L = {w ∈{0, 1}∗| w ist ein Palindrom }

Comments

Original in der Mathelounge:

Titel: Zeigen Sie, dass die folgende Sprache in Polynomialzeit entscheidbar ist: L = {w ∈{0, 1}∗| w ist ein Palindrom }.

Stichworte: formalesprachen

Frage:

Zeigen Sie, dass die folgende Sprache in Polynomialzeit entscheidbar ist: L = {w ∈{0, 1}∗| w ist ein Palindrom }. Skizzieren Sie dazu eine deterministische 1-Band TuringMaschine ML, welche L entscheidet und begründen Sie die Laufzeit von ML.

Code:

L = {w ∈{0, 1}∗| w ist ein Palindrom }

---

Das ist ein Problem aus der "Theoretischen Informatik".

Vielleicht wäre die Frage da besser platziert.

Answer 1

Die Turingmaschine merkt sich das erste Zeichen, löscht es, merkt sich das letzte Zeichen, löscht es und vergleicht die gemerkten Zeichen. Das wird so lange wiederholt bis das Band leer ist.