IIm18-Kreativaufgabe5

Wiki-Quelltext dieser Seite.

== Ü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.

<popup name="Lösungsideen">
    ''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.
</popup>

Erweiterung der TM