IIm18-Kreativaufgabe5

Übungsaufgabe 1, VL S.14

Eine TM soll überprüfen ob w die Form uu besitzt. Für u gilt a^ib^ic^i, bei Korrektheit von w soll u auf dem Band hinterlassen werden.

Anmerkung: der Teil der TM, welcher das Wort w auf die Form uu prüft ist schon in den Vorlesungsfolien gegeben. Es geht primär darum u nach akzeptieren von w, auf dem Band zu hinterlassen. Hierzu kann man unterschiedlich vorgehen, im Folgenden werden die Lösungsideen vorgestellt.

   1. Die erste Idee besteht darin bei jeder iteration in der die TM w auf die Form uu prüft, die TM an der Stelle zu erweitern und das u entsprechend zu hinterlassen.
   2. Man könnte auch den Ansatz verfolgen wobei die TM erst w akzeptiert, am Ende steht hier ein Wort auf dem Band, der Form xxxxxx auf dem Band. Hier könnte man die Hälfte des
   Wortes löschen und dann beginnen das verbleibende u von vorne und hinten zu füllen.

Erweiterung der TM