Übungen
Aufgabe 1: Sprache erkennen
Man kann zeigen, dass die Sprache L = {anbncn | n = 1, 2, 3, ...} nicht mit einem Kellerautomaten erkannt werden kann. Diese Sprache besteht aus Wörtern, die wie folgt aufgebaut sind:
abc, aabbcc, aaabbbccc, aaaabbbbcccc, ...
Zeige, dass diese Sprache mit einer Turingmaschine erkannt werden kann. Erweitere hierzu die Turingmaschine zur Erkennung von L = {anbn | n = 1, 2, 3, ...}.
Aufgabe 2: "1 anhängen"
(a) Erstelle zunächst eine Turingmaschine, die auf ein leeres Band genau eine 1 schreibt und dann stoppt.
(b) Auf dem Band steht eine unbestimmte Anzahl an 1en, der Kopf steht am linken Rand dieser Reihe von 1en. Die Turingmaschine soll dann am rechten Rand eine weitere 1 ergänzen und dann stoppen.
Aufgabe 3: Invertieren
Die Bandbeschriftung besteht aus 0en und 1en. Dabei ist nicht bekannt, wo der Kopf steht, wie lange die Bandbeschriftung ist und auch nicht, wieviele 0en und 1en vorhanden sind und in welcher Reihenfolge diese auf dem Band stehen. Die Turingmaschine soll nun die Beschriftung invertieren, d. h. aus jeder 0 eine 1 machen und entsprechend aus jeder 1 eine 0 machen, dann soll die Maschine stoppen.
Aufgabe 4: "0 oder 1 anhängen"
Die Bandbeschriftung besteht aus 0en und 1en. Dabei ist nicht bekannt, wie lange die Bandbeschriftung ist und auch nicht, wie viele 0en und wie viele 1en enthalten sind und in welcher Reihenfolge sie auf dem Band stehen. Der Kopf steht am linken Rand der Bandbeschriftung. Die Turingmaschine soll nun am rechten Rand der Bandbeschriftung ein weiteres Zeichen ergänzen: Steht ganz rechts auf dem Band eine 0, so soll eine 1 angehängt werden. Steht ganz rechts auf dem Band eine 1, so soll eine 0 angehängt werden.
Aufgabe 5: "Paritätsbit"
Bei Datenübertragungen oder im Hauptspeicher wird zur Fehlererkennung häufig die Parität genutzt. Gerade Parität heißt dabei, dass die Anzahl der 1en gerade ist, ungerade Parität bedeutet entsprechend eine ungerade Anzahl an 1en. Dazu wird die Anzahl der 1en festgestellt und in einem zusätzlichen Paritätsbit eine 0 oder 1 gespeichert, sodass die Parität den gewünschten Wert annimmt. Die zu konstruierende Turingmaschine startet auf ein Band, das mit einer ununterbrochenen Folge von 0en und 1en beschriftet ist. Die Länge der Beschriftung ist unbekannt, die Anzahl der 0en und 1en auch sowie in welcher Reihenfolge sie auf dem Band stehen. Der Kopf steht zu Beginn am linken Rand der Bandbeschriftung. Die Turingmaschine soll am rechten Rand der Bandbeschriftung ein weiteres Zeichen schreiben, sodass anschließend die Anzahl der auf dem Band stehenden 1en gerade ist.
Aufgabe 6: "Dualzähler"
Die Bandbeschriftung besteht zunächst nur aus einer 0. Die Turingmaschine soll dann als Dualzähler arbeiten, die Bandbeschriftung soll also der Reihe nach die Werte 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, ... annehmen.