Theoretische Informatik - Aufgaben

Aufgabe:  

Gegeben ist die Sprache

L  =  { ww^Rw  |  w ∈ {a, b}* }

Hierbei ist w^R das gespiegelte (d.h. rückwärts gelesene) Wort w.

 

1. Beschreiben Sie informell, wie eine linear beschränkte Turing­maschine die Sprache L erkennt.
2. Erstellen Sie mit dem Turing­maschinen-Simulator eine linear beschränkte Turing­maschine, die L erkennt. Testen Sie Ihre Turing­maschine mit dem Eingabewort abbaab.