0 Daumen
140 Aufrufe

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 }

von

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.

1 Antwort

+1 Daumen

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.

von 3,5 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community