Grundlagen der theoretischen Informatik, SS 2001 — 6. Übungsblatt

Abgabe bis Dienstag, 12. Juni 2001

30. (6 Punkte) Binäre Addition.

Konstruieren Sie eine Turingmaschine, die die Summe zweier Zahlen in Binärdarstellung berechnet. Bei Eingabe von bin(x)#bin(y)$ soll die Maschine mit der Ausgabe bin(x + y)#bin(y)$ und dem Kopf auf dem ersten Eingabesymbol halten. Dabei soll die Notation bin(x) ∈ {0, 1}^{∗} eine Darstellung von x ∈ ℕ in Binärdarstellung darstellen. Der Automat soll am Ende in einen Zustand q_{F} übergehen und anhalten. Ein eventueller Bandinhalt rechts vom $-Zeichen soll unverändert stehengelassen werden.

Beschreiben Sie Ihren Algorithmus zunächst in Worten.

Geben Sie die ersten 15 und die letzten 10 Konfigurationen Ihrer Turingmaschine bei Eingabe von 101#11$ an.

31. (0 Punkte) Multiplikation.

Konstruieren Sie eine Turingmaschine, die zwei ”unäre“ Zahlen multipliziert. Bei Eingabe von 0^{m}1^{n} soll die Ausgabe 0^{mn} berechnet werden.

32. (0 Punkte)

(a) Entwerfen Sie eine Turingmaschine, die die Sprache { 0^{n}1^{n}0^{n} | n ≥ 0 } akzeptiert.

(b) Entwerfen Sie eine Turingmaschine für dieselbe Sprache, die mit dem Bandalphabet Γ = {0, 1, B} auskommt. (Hinweis: Sie können ein größeres Bandalphabet ”simulieren“, indem Sie es ”binär kodieren“. Dabei wird jeweils eine feste Anzahl von Feldern des Bandes zu einer logischen Einheit zusammengefasst.)

33. (5 Punkte) Definieren Sie formal die Nachfolgerrelation xqy ⊢ x′q′y′ für Konfigurationen einer Turingmaschine. (q, q′ ∈ Q, x ∈ {ε} ∪ (Γ − {B})Γ^{∗}, y ∈ {ε} ∪ Γ^{∗}(Γ − {B}).)

34. (0 Punkte) Speicherzugriff (Tabellenzugriff) über Adressen.

(a) Lesen aus einer Tabelle.

Bei Eingabe von

x = #x_{1}|y_{1}#x_{2}|y_{2}# … #x_{n}|y_{n}$x_{0}

mit n ≥ 0, x_{k}, y_{k} ∈ {0, 1}^{∗} soll die Ausgabe x|y berechnet werden. Dabei ist y = y_{i} für den größten Index i ≤ n mit x_{i} = x_{0}, und y = 0, falls kein solches i existiert.

(b) Löschen aus einer Tabelle.

Bei den gleichen Angaben wie oben soll die Ausgabe

x = #x_{1}|y_{1}# … #x_{i−1}|y_{i−1}#x_{i+1}|y_{i+1}# … #x_{n}|y_{n}$x_{0}

berechnet werden. Wenn kein passender Index i existiert, soll die Eingabe unverändert gelassen werden.

35. (4 Punkte) Beweisen oder widerlegen Sie:

(a) (4 Punkte) Das Komplement einer entscheidbaren Sprache ist entscheidbar.

(b) (0 Punkte) Die Vereinigung zweier entscheidbarer Sprache ist entscheidbar.

(c) (0 Punkte) Das Komplement einer unentscheidbaren Sprache ist unentscheidbar.

(d) (0 Punkte) Die Vereinigung zweier unentscheidbarer Sprache ist unentscheidbar.