Grundlagen der theoretischen Informatik, SS 2005 — 7. Übungsblatt

Abgabe bis Montag, 13. Juni 2005, 10:15 Uhr

49. Ist es entscheidbar, ob eine Turingmaschine das leere Wort akzeptiert? Ist es entscheidbar, ob eine Turingmaschine alle Wörter (also Σ^{∗}) akzeptiert?

50. Lösen Sie das Post’sche Korrespondenzproblem über einem einelementigen Alphabet.

51. Lösen Sie das Post’sche Korrespondenzproblem für folgende Eingaben:

(a) x_{1}, …, x_{5} = abb, a, bab, baba, aba; y_{1}, …, y_{5} = bbab, aa, ab, aa, a.

(b) x_{1}, …, x_{5} = a, baa, abab, aabb, abb; y_{1}, …, y_{5} = ab, ba, bbaa, bbba, bba.

(c) x_{1}, …, x_{10} = d, de, deh, deh, deh, deha, deha, wa, wa, wah; y_{1}, …, y_{10} = add, e, de, d, deha, eh, d, w, wah, wa; Welches sind die zwei kürzestes Lösungen?

(d) (zum Tüfteln für alle, denen das Post’sche Korrespondenzproblem zu leicht vorkommt) x_{1}, …, x_{4} = 001, 01, 01, 10; y_{1}, …, y_{4} = 0, 011, 101, 001.

52. Zeigen Sie, dass es unendlich viele Lösungen gibt, wenn das Post’sche Korrespondenzproblem eine Lösung hat.

53. (a) (5 Punkte) Die algorithmische Reduzierbarkeit zwischen Problemen ist transi-

tive: Aus A < B und B < C folgt A < C. Ist sie eine Ordnungsrelation?

(b) (5 Punkte) Beweisen Sie: Wenn A ein beliebiges entscheidbares Problem ist, so ist es auf das Halteproblem H reduzierbar: A < H.

54. Wie kann man jede Turingmaschine ohne Zeitverlust durch eine Turingmaschine simulieren, die sich nie über das erste Eingabezeichen nach links hinausbewegt?

55. (5 Punkte) Wenn eine Turingmaschine (Q, Σ, Γ, δ, q_{0}, B, F) ein Wort w in t Schritten akzeptiert und sie dabei nur die ersten s Felder des Bandes besucht und sich nie über das erste Eingabezeichen nach links hinausbewegt, dann ist t ≤ |Q| · s · |Γ|^{s}.

56. Betrachten Sie die ”Fleißige-Biber-Funktion“ für Programme in der Programmiersprache Schleife aus Aufgabe 1d, eingeschränkt auf Programme, in denen die Schleifenanweisungen höchstens bis zu einer vorgegebenen Tiefe k geschachtelt sind.

(a) Beweisen Sie, dass diese Funktion berechenbar ist.

(b) Beweisen Sie, dass diese Funktion für ein festes k ≥ 1 nicht mit einem Schleife-Programm der Schachtelungstiefe k berechnet werden kann.

(c) Was ist die Fleißige-Biber-Funktion für k = 0 (Programme ohne Schleife)? Was ist das kürzeste Programm zur Berechnung dieser Funktion?

57. Entwerfen Sie eine kontextsensitive Grammatik für die Sprache { a^{n}b^{n}c^{n} | n ≥ 1 }.

58. Der erste Satz dieser Aufgabe ist ein Beispiel eines grammatikalisch korrekten Satzes. Analysieren Sie diesen Satz gemäß der nachstehenden rudimentären Grammatik:

S → NG VG, NG → NG Att, NG → Art NG′, NG → NG′, NG′ → Adj NG′, NG′ → N, NG → Pro, Att → NG, Att → Präp NG, VG → V, VG → V Obj, VG → V Pr, VG → VG Erg, Obj → NG, Erg → Präp NG, Pr → Adj, Pr → NG, Adj → Adv Adj.

(S = Satz, NG = Nominalgruppe, NG′ = Nominalgruppe ohne Artikel, VG = Verbgruppe, Att = Attribut, Art = Artikel, Adj = Adjektiv, Adv = Adverb, N = Hauptwort (Nomen), Pro = Pronomen, Obj = Objekt, Erg = Modalobjekt, Pr = Prädikat.) Warum passt der zweite Satz dieser Aufgabe nicht zu dieser Grammatik?