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

(freiwillige Vorübungen)

1. (0 Punkte) Die Programmiersprache Schleife hat die folgenden einfachen Regeln:

• Es gibt einen unendlichen Vorrat an Variablen X0, X1, X2, X3, …, die beliebige natürliche Zahlen (≥ 0) speichern können.

• Es gibt die einfachen Anweisungen Xi = 0 (Inititalisierung), Xi = Xj (Kopieren), Xi = Xi + 1 (Hinaufzählen) und Xi = Xi - 1 (Herunterzählen). (Beim Herunterzählenwird Xi unverändert gelassen, wenn es den Wert 0 hat, weil die Variablen keine negativen Werte enthalten können.)

• Außerdem gibt es eine Schleifenanweisung:

         WIEDERHOLE Xi MAL

Anweisungsfolge

         SCHLEIFENENDE

Wenn die Variable Xi zu Beginn der Ausführung den Wert n hat, wird die Schleife n-mal wiederholt, auch wenn Xi zwischendurch geändert wird. Schleifen können auch geschachtelt sein.

Es gibt keine Ein- und Ausgabeanweisungen. Die Eingabeparameter eines Programms stehen zu Beginn in den ersten Variablen X0, X1, …. Alle übrigen Variablen sind zu Beginn auf 0 gesetzt. Das Ergebnis des Programms ist der Wert, der am Ende in X0 steht.

Das folgende Programm berechnet zum Beispiel die Summe von zwei Zahlen X0 und

X1:
       WIEDERHOLE X1 MAL
         X0 = X0 + 1
       SCHLEIFENENDE

(a) Schreiben Sie ein Programm zur Berechnung des Produktes von X0 und X1.

(b) Schreiben Sie ein Programm, dass den Rest der Division von X1 durch X0 berechnet. (Wenn X0 = 0 ist soll das Ergebnis X1 sein.)

(c) Schreiben Sie ein Programm zur Berechnung von 2^{X0}.

(d) Schreiben Sie ein Programm, dass mit allen Variablen auf Null beginnt, aus höchstens n = 2, 3, 4, 5, 6, 7 Anweisungen besteht, und am Ende einen möglichst großen Wert in X0 hat. (Dabei gilt ein WIEDERHOLE-SCHLEIFENENDE-Paar als eine einzige Anweisung.)

(e) Die Programmiersprache Schleife++ hat zusätzlich bedingte Anweisungen:

         IF Xi>Xj THEN

Anweisungsfolge

         ENDIF

Wie kann mein ein solches Programm durch Eliminieren aller bedingten Anweisungen in ein Schleife-Programm übersetzen?

2. (0 Punkte) Für ein Alphabet Σ mit k Elementen ist Σ^{∗} ist die Menge der Wörter (Folgen), die man aus den Buchstaben von Σ bilden kann.

(a) Wieviele Wörter in Σ^{∗} haben die Länge n (bestehen aus n Buchstaben)?

(b) Wieviele Palindrome in Σ^{∗} haben die Länge n? (Ein Palindrom ist ein Wort, das von vorne und von hinten gelesen gleich ist.)

3. (0 Punkte) Durch wiederholte Anwendung des Homomorphismus

0 → 01, 1 → 0

auf das Ausgangswort 0 erhält man die Folge der Wörter

w_{0} = 0, w_{1} = 01, w_{2} = 010, w_{3} = 01001, w_{4} = 01001010, w_{5} = 0100101001001, …

(a) Beschreiben Sie, was ein Homomorphismus ist, und was die Anwendunge eines Homomorphismus auf ein Wort (über einem gegebenen Alphabet) bedeutet. (Lassen Sie sich dabei von diesem Beispiel und dem Beispiel in der nächsten Aufgabe leiten, anstatt gleich im Lehrbuch nachzuschlagen.)

(b) Welche Länge hat das Wort w_{n}?

(c) Jedes Wort ist ein Anfangsstück (Präfix) des darauffolgenden Wortes, sodass die Folge gegen ein unendliches Wort w_{∞} “konvergiert”. Wieviele verschiedene Teilwörter (zusammenhängende Teilfolgen) der Längen n = 1, 2, 3, 4, 5 enthält w_{∞}?

(d) (*) Gegen welchen Wert konvergiert der Anteil der Einsen in w_{n} an der Gesamtzahl der Symbole?

4. (0 Punkte) Durch wiederholte Anwendung des Homomorphismus

0 → 100, 1 → 001

auf das Ausgangswort 0 erhält man die Folge der Wörter

w_{0} = 0, w_{1} = 100, w_{2} = 001100100, w_{3} = 100001001001100100001100100, …

(a) Welche Länge hat das n-te Wort?

(b) Gegen welchen Wert konvergiert der Anteil der Einsen?

(c) Die Wörter, die mit 0 beginnen, konvergieren gegen ein unendliches Wort. Wieviele verschiedene Teilwörter der Längen n = 1, 2, 3, 4, 5 enthält dieses Wort?

(d) Im Gegensatz zur vorigen Aufgabe ist hier nicht jedes Wort ist eine Verlängerung des vorhergehenden Wortes. An welcher Eigenschaft des Homomorphismus mag das liegen?

Kriterien zur Erlangung eines Scheines:

1. In jeder Vorlesungswoche muss eine Übungsaufgabe gelöst und abgegeben werden. Insgesamt müssen 60 % der Gesamtpunktezahl der Übungen erreicht werden. Die Übungsaufgaben können in Zweiergruppen (oder einzeln) abgegeben werden.

2. Von jeweils zwei aufeinanderfolgenden Übungszetteln müssen mindestens je 30 % der Punkte erreicht werden. (Eine einmalige Ausnahme wird toleriert.)

3. Aktive Teilnahme an den wöchentlichen Tutorien und einmaliges Vorrechnen eines Übungsbeispiels pro Person, nach vorheriger Einteilung in einer Liste. Da die Aufgaben gemäß Punkt 1 dazu nicht ausreichen, gibt es auf den Übungsbättern zusätzliche Aufgaben für diesen Zweck (und auch einfach zum Üben).

4. 50 % der Punkte bei der Zwischenklausur und 50 % der Punkte bei der Abschlussklausur (oder bei der entsprechenden Nachklausur).

Der Schein wird benotet. Die Note ergibt sich aus den Klausuren.

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

Abgabe bis Montag, 25. April 2005, 10:15 Uhr

5. (10 Punkte) Beschreiben Sie die Sprache L, die durch den regulären Ausdruck

0^{∗}(0 + 10^{∗}1)^{∗}(ε + 0 + 00)

gegeben ist. (Alle Worte in L haben eine sehr charakteristische Eigenschaft. Welche?) Beweisen Sie Ihre Behauptung! Gibt es einen einfacheren regulären Ausdruck für diese Sprache?

6. (0 Punkte)

(a) Geben Sie einen regulären Ausdruck an, der genau die Worte w über Σ mit der folgenden Eigenschaft beschreibt: ”w enthält keine zwei unmittelbar aufeinanderfolgenden gleichen Symbole,“ und zwar für Σ_{2} = {a, b}, Σ_{3} = {a, b, c}, und für Σ_{4} = {a, b, c, d}. Beweisen Sie, dass Ihr Ausdruck wirklich diese Sprache beschreibt!

(b) Lösen Sie dieselbe Aufgabe für die folgende Eigenschaft: ”Jedes Symbol in w steht neben einem gleichen Symbol.“ (Zum Beispiel hat das Wort aaabbcccaa diese Eigenschaft.)

(c) (schwierig) Wieviele Wörter der Länge n enthält die Sprache aus Aufgabe (b), für Σ_{2} und Σ_{3}?

7. (0 Punkte)

(a) Codieren Sie das Alphabet {a, b, …, z} durch Binärworte, so dass jedes codierte Wort wieder eindeutig decodierbar ist! (Eine ungeeignete Codierung wäre z.B. a ↦ 0, b ↦ 01, c ↦ 100, etc. In diesem Fall könnte nämlich 0100 von ac oder von baa herstammen.) Zeigen Sie, dass Ihre Codierung die gewünschte Eigenschaft hat.

(b) Das Alphabet Σ = {a, b} sei durch a ↦ 0 und b ↦ 010 codiert. Zeigen Sie, dass diese Codierung eindeutig decodierbar ist!

8. (Zusatzfrage, 10 Punkte) Welche der folgenden Gleichungen gelten für alle regulären Ausdrücke?

(a) (AB)C = A(BC)

(b) (A^{∗})^{∗} = A^{∗}

(c) (A + B)^{∗} = A^{∗} + B^{∗}

(d) (A^{∗}B^{∗})^{∗} = (A + B)^{∗}

Beweisen Sie Ihre Antworten.Wenn eine Beziehung nicht als Gleichung gilt, in welchen Fällen gilt dann eine Inklusionsbeziehung (⊆ oder ⊇)?

9. (0 Punkte) Geben sie einen regulären Ausdruck an, der alle Wörter über Σ = {0, 1} beschreibt, die 0101 nicht als Teilwort enthalten.

10. (0 Punkte) Konstruieren Sie einen regulären Ausdruck für die Sprache L_{1} der Wörter über {0, 1}, bei denen auf jedes Vorkommen der Teilfolge 0011 unmittelbar die Teilfolge 1100 anschließt.

Zum Beispiel ist w_{1} = 0001111100 ∉ L_{1}, w_{2} = 01011001111001111000 ∈ L_{1}, w_{3} = 0010 ∈ L_{1}, und w_{4} = 00111100011 ∉ L_{1}. Erklären Sie Ihren Ausdruck. (Ein formaler Korrektheitsbeweis ist nicht erforderlich.)

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

Abgabe bis Montag, 2. Mai 2005, 10:15 Uhr

11. Kommutierende Wörter: Wieviele Paare von Wörter a ∈ Σ^{3} und b ∈ Σ^{2} mit der Eigenschaft ab = ba gibt es? Wieviele Paare von Wörter a ∈ Σ^{6} und b ∈ Σ^{9} mit der Eigenschaft ab = ba gibt es? Wie ist es allgemein für a ∈ Σ^{m} und b ∈ Σ^{n}? Wodurch kann man solche Wortpaare charakterisieren?

12. Eine Kongruenzrelation ∼ auf einer Menge Σ^{∗} von Wörtern ist eine Äquivalenzrelation mit folgender zusätzlicher Eigenschaft:

a ∼ b ∧ c ∼ d ⟹ ac ∼ bd.

Welche der folgenden Relationen sind Kongruenzrelationen? Die Beziehung a ∼ b soll genau dann gelten, wenn folgende Bedingung erfüllt ist:

(a) a und b haben die gleiche Anzahl von Nullen und die gleiche Anzahl von Einsen.

(b) a = b = ε oder a ≠ ε ≠ b und a und b haben denselben Anfangsbuchstaben.

(c) a = ε oder b = ε oder a ≠ ε ≠ b und a und b haben denselben Anfangsbuchstaben.

(d) das Teilwort 100 kommt in a und b gleich häufig vor.

13. Schreiben Sie ein Programm in Haskell (oder Java), das für einen endlichen Automaten (in einer geeigneten Darstellung) und ein gegebenes Wort entscheidet, ob es vom Automaten akzeptiert wird.

14. (a) (5 Punkte) Konstruieren Sie einen endlichen Automaten, der die durch 5 teilbaren

Binärzahlen akzeptiert. Das höchstwertige Bit wird dabei zuerst eingelesen.

(b) (5 Punkte) Konstruieren Sie einen deterministischen endlichen Automaten, der genau jene Wörter über dem Alphabet {a, b, c, d} akzeptiert, die das Teilwort abacabadabaca enthalten.

(c) (0 Punkte) Konstruieren Sie einen endlichen Automaten, der die Wörter akzeptiert, die das Teilwort abacabadabaca nicht enthalten.

Erläutern Sie Ihre Automaten mit einigen Sätzen. Zeichnen Sie Zustandsdiagramme.

15. Konstruieren Sie einen äquivalenten deterministischen Automaten für den nichtdeterministischen endlichen Automaten mit Σ = {0, 1}, Q = {a, b, c}, Q_{0} = {a}, F = {a} und

δ = {(a, 0, a), (a, 0, b), (b, 1, b), (b, 1, c), (c, 0, c), (c, 0, a)}.

16. (Zusatzaufgabe, 0 Punkte) Beweisen Sie, dass die von einem DEA akzeptierten Sprachen (die regulären Sprachen) unter Präfixbildung abgeschlossen sind: Wenn L eine solche Sprache ist, dann gibt es auch einen DEA, der

L′ = { x | es gibt ein y mit xy ∈ L }

akzeptiert.

17. Konstruieren Sie einen endlichen Automaten ohne ε-Übergänge für die Sprache

(a + ba)^{+}(b + ab)^{∗} + (bb)^{∗}a^{+}(bb)^{∗}.

18. Für einen Zustand q ∈ Q des DEA M = (Q, Σ, δ, q_{0}, F) sei die Sprache L_{q}(M) so

definiert:

L_{q}(M) = { w ∈ Σ^{∗} | δ(q_{0}, w) = q }

Beweisen Sie: Wenn w_{1}, w_{2} ∈ L_{q}(M) sind, dann gilt für alle x ∈ Σ^{∗}:

w_{1}x ∈ L(M) ⟺ w_{2}x ∈ L(M)

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

Abgabe bis Montag, 9. Mai 2005, 10:15 Uhr

19. (10 Punkte) L_{1} sei eine reguläre Sprache über dem Alphabet {0, 1}, und

L_{2} = { w_{1}0w_{2}0 … 0w_{n} | w = w_{1}w_{2} … w_{n} ∈ L_{1}, n ≥ 1, w_{i} ∈ {0, 1} }

sei die Sprache, wo zwischen je zwei Buchstaben eine Null eingefügt ist. (Am Ende wird keine Null angehängt!) Beweisen Sie, dass L_{2} ebenfalls regulär ist.

20. (a) Das Produkt von Automaten.

Konstruieren Sie zu zwei gegebenen DEAs M^{1} = (Q^{1}, Σ, δ^{1}, q_{0}^{1}, F^{1}) und M^{2} = (Q^{2}, Σ, δ^{2}, q_{0}^{2}, F^{2}) einen DEA für die Sprache L(M^{1}) ∩ L(M^{2}).

(b) Konstruieren Sie einen DEA für die Sprache L(M^{1}) ∪ L(M^{2}).

21. (a) Konstruieren Sie einen deterministischen endlichen Automaten, der die durch 5 teilbaren Binärzahlen akzeptiert. Diesmal soll das niederwertigste Bit als erstes gelesen werden.

(b) Konstruieren Sie endliche Automaten für die durch 6 teilbaren Dezimalzahlen, die (1) von der höchsten zur niedrigsten Stelle (2) von der niedrigsten zur höchsten Stelle gelesen werden.

22. Ist die Nerode-Relation einer Sprache L immer eine Kongruenzrelation? Ist die Nerode-Relation einer regulären Sprache L immer eine Kongruenzrelation?

23. Welche der folgenden Sprachen über Σ = {0, 1} sind regulär?

(a) Die Sprache L_{1} = { x | x = x^{R} } der Palindrome

(b) L_{2} = { 0^{i^{2}} | i ≥ 1 }

(c) L_{3} = { x | x enthält mindestens so viele Nullen wie Einsen }

(d) L_{4} = { x | die Anzahl der Nullen von x unterscheidet sich um höchstens um 1 von der Anzahl der Einsen }

(e) L_{5} = { x | in jedem Präfix von x unterscheidet sich die Anzahl der Nullen höchstens um 1 von der Anzahl der Einsen }

(f) L_{6} = { x | in jedem Präfix von x unterscheidet sich die Anzahl der Nullen höchstens um 2 von der Anzahl der Einsen }

24. (Zusatzaufgabe, 0 Punkte) Für einen Homomorphismus h: Σ^{∗} → Δ^{∗} und eine Sprache L ⊆ Σ^{∗} bezeichnet h(L) die Sprache

h(L) := { h(x) | x ∈ L }.

Beweisen Sie, dass das Bild h(L) einer regulären Sprache L unter einem Homomorphismus h regulär ist.

25. (*) Beweisen Sie: Wenn L ∈ Δ^{∗} regulär ist und h: Σ^{∗} → Δ^{∗} ein Homomorphismus ist, ist auch die folgende Sprache regulär:

h^{−1}(L) := { x ∈ Σ^{∗} | h(x) ∈ L }

26. Welche der Sprachen h_{j}(L_{i}) sind regulär, wenn L_{i} eine der Sprachen aus Aufgabe 23 ist und der Homomorphismus h_{j} folgendermaßen gegeben ist?

(a) h_{1}(0) = a, h_{1}(1) = b, Δ = {a, b}.

(b) h_{2}(0) = 1, h_{2}(1) = 1.

(c) h_{3}(0) = 01, h_{3}(1) = ε.

27. Konstruieren Sie den Minimalautomaten für den Automaten aus Aufgabe 15.

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

Abgabe bis Dienstag, 17. Mai 2005, 10:15 Uhr

27.

Konstruieren Sie für den DEA M = (Q = {a, b, c}, Σ = {0, 1}, δ, a, {b}) einen regulären Ausdruck, der die von M akzeptierte Sprache beschreibt. Die Übergangsfunktion δ ist in der nebenstehenden Tabelle angegeben.

Wenden Sie den in der Vorlesung vorgestellten Algorithmus von Kleene auf die Zustände einmal in der Reihenfolge a, b, c und dann in der Reihenfolge c, a, b an. Vereinfachen Sie dabei die Zwischenergebnisse, so gut es geht. Versuchen Sie auch, ”direkt“ durch Betrachten des Zustandsdiagramms und Nachdenken einen möglichst einfachen regulären Ausdruck zu finden.

\begin{matrix}δ & 0 & 1 \\ a & a & b \\ b & c & b \\ c & b & a \end{matrix}

28. Erweitern Sie das in der Vorlesung vorgestellte lex-Programm^{1} zur Addition aller in der Eingabe vorkommenden Zahlen um folgende Funktionen:

(a) Es sind auch Zahlen in Exponentialnotation wie zum Beispiel 0.54e-7 = 0,54 × 10^{−7} zugelassen.

(b) Bei Eingabe von * wird die nächste Zahl nicht addiert, sondern multipliziert.

(c) Bei Eingabe von = wird das bisherige Ergebnis ausgedruckt.

(d) Es werden zusätzlich auch Kommentare im Stil von Haskell verstanden: Alles zwischen -- und dem Ende der Zeile wird ignoriert.

Die obigen Angaben lassen einige Fragen offen, zum Beispiel die Wechselworkung zwischen den verschiedenen Arten von Kommentaren. Ergänzen Sie zunächst die obige Aufgabenspezifikation in Worten, sodass das Verhalten des Programmes eindeutig daraus hervorgeht. Ihr Programm sollte dann dieser Spezifikation entsprechen.

29. Konstruieren Sie einen regulären Ausdruck für die Sprache L_{6} von Aufgabe 23f.

30. (Zusatzaufgabe) Konstruieren Sie DEAs und NEAs für folgende Sprachen über {0, 1}:

(a) die Wörter, deren vierter Buchstabe eine 0 ist;

(b) die Wörter, deren viertletzter Buchstabe eine 0 ist.

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

32. (10 Punkte) Multiplikation. Konstruieren Sie eine Turingmaschine, die zwei ”unäre“ Zahlen multipliziert. Bei Eingabe von 0^{m}#0^{n} soll die Ausgabe 0^{mn} berechnet werden.

33. Binäre Multiplikation.

In der Vorlesung wurde eine Turingmaschine vorgestellt, die die Summe zweier Zahlen in Binärdarstellung berechnet. Bei Eingabe von bin(x)#bin(y)$ und Start im Zustand q_{0} hält die Maschine im Zustand q_{F} mit der Ausgabe bin(x+y)#bin(y)$ und dem Kopf auf dem ersten Eingabesymbol. (Die Notation bin(x) ∈ {0, 1}^{∗} ist eine Darstellung von x ∈ ℕ in Binärdarstellung.) Der Bandinhalt rechts vom $-Zeichen bleibt dabei unverändert stehen. Erweitern Sie diese Maschine zu einer Maschine, die zwei Binärzahlen multipliziert: Bei Eingabe von bin(x)$bin(y) soll die Maschine die Ausgabe bin(x · y) berechnen. Ihre Maschine soll die Addiermaschine aus der Vorlesung als ”Unterprogramm“ benutzen, indem Sie an geeigneten Stellen in den Zustand q_{0} übergeht. Der Zustand q_{F} ist dann kein Haltezustand mehr, sondern die Rechnung wird danach fortgesetzt. Beschreiben Sie Ihren Algorithmus zunächst in Worten.

1http://www.inf.fu-berlin.de/lehre/SS05/GTI/flex/summe.flex

34. (Zusatzaufgabe, 0 Punkte) Tabellenzugriff über Adressen, Simulation eines RAM-Speichers durch eine Turingmaschine. Bei Eingabe des Wortes

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.

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

tiert.

(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.)

36. Fleißige Biber (siehe auch Aufgabe 1d). Entwerfen Sie eine Turingmaschine mit 2 Zuständen (zusätzlich zum Haltezustand) und dem Bandalphabet Γ = {1, B}, die mit dem leeren Band beginnt, nach endlich vielen Schritten anhält, und dabei eine möglichst lange fortlaufende Folge von Einsen auf das Band schreibt.

37. Eine Funktion f: ℕ → ℕ heißt Schleife-berechenbar, wenn es ein Programm in der Programmiersprache Schleife aus Aufgabe 1 gibt, das bei Eingabe von n in der Variablen X0 (und mit allen übrigen Variablen auf 0 gesetzt) mit dem Wert f(n) in der Variablen X0 terminiert. Beweisen Sie: Wenn die Funktionen f und g (durch Programme der Länge k_{1} und k_{2}) Schleife-berechenbar sind, dann ist auch die Funktion f ∘ g: n ↦ g(f(n)) Schleife-berechenbar, und zwar durch ein Programm der Länge k_{1} + k_{2}.

38. Überlegen Sie, wie man Schleife-berechenbare Funktionen f: ℕ → ℕ mit Java oder Haskell berechnen könnte. Diskutieren Sie, welche Möglichkeiten von Java oder Haskell über die Möglichkeiten der Programmiersprache Schleife wesentlich hinausgehen, sodass man offenbar nicht jedes Java- oder Haskell-Programm zu Berechnung einer Funktion in Schleife übersetzen kann. (Die Objektorientierung gehört nicht zu diesen wesentlichen Möglichkeiten.)

39. (Zusatzaufgabe, 5 Punkte) Wenn die Taste - auf der Tastatur kaputt ist, steht der Befehl Xi = Xi - 1 zum Herunterzählen in der Programmiersprache Schleife nicht zur Verfügung. Wie kann man diesen Befehl durch die übrigen Befehle simulieren?

40. (5 Punkte) Wie kann man für zwei gegebene reguläre Ausdrücke entscheiden, ob sie dieselbe Sprache darstellen? Skizzieren Sie einen Lösungsalgorithmus in groben Zügen. Dabei dürfen Sie Ergebnisse aus der Vorlesung und von anderen Übungsaufgaben verwenden.

41. Beweisen oder widerlegen Sie:

(a) Das Komplement einer entscheidbaren Sprache ist entscheidbar.

(b) Die Vereinigung zweier entscheidbarer Sprache ist entscheidbar.

(c) Das Komplement einer unentscheidbaren Sprache ist unentscheidbar.

(d) Die Vereinigung zweier unentscheidbarer Sprache ist unentscheidbar.

42. Welche der beiden folgenden Aussagen sind wahr? Beweisen oder widerlegen Sie sie. (a) Wenn L_{1} und L_{2} entscheidbar sind, dann ist auch L_{1}L_{2} entscheidbar.

(b) Wenn L_{1} und L_{2} rekursiv aufzählbar sind, dann ist auch L_{1}L_{2} rekursiv aufzähl-

bar.

43. (10 Punkte) D = { w_{i} | M_{i} akzeptiert w_{i} nicht } bezeichnet die Diagonalsprache und D̄ ihr Komplement.

(a) Zeigen Sie, dass die Sprache D̄ rekursiv aufzählbar ist.

(b) Zeigen Sie, dass die Sprache 0D ∪ 1D̄ nicht rekursiv aufzählbar ist.

44. (2 Zusatzpunkte) Eine andere Konstruktion einer unentscheidbaren Sprache.

U′ := { ⟨M⟩w | M akzeptiert das Wort ⟨M⟩w nicht }

(Der Beweis geht ähnlich wie bei der Diagonalsprache D.)

45. Welche der folgenden Sprachen sind rekursiv, welche sind rekursiv aufzählbar? (a) L_{1} = { 0^{k}⟨M⟩w | M akzeptiert w nach höchstens k Schritten. }

(b) L_{2} = { 0^{k}⟨M⟩w | M hat w nach k Schritten noch nicht akzeptiert. }

(c) L_{3} = Σ^{∗} − (L_{1} ∪ L_{2})

(d) L_{4} = { 0^{k}⟨M⟩w | M akzeptiert w nach mehr als k Schritten. }

46. Beweisen Sie, dass die Sprache L = { 0^{i} | i ≥ 0, das Teilwort 0^{i}123 kommt in der Dezimaldarstellung von π unendlich oft vor } entscheidbar ist. (Sie müssen dazu nichts über π wissen, nur logisch überlegen können. Wie kann L aussehen?)

47. Welche der folgenden Aussagen sind wahr, und welche sind falsch? Welche Aussagen sind trivial, und welche sind absurd?

(a) Jede Teilmenge einer rekursiven Sprache ist rekursiv.

(b) Jede Teilmenge einer rekursiv aufzählbaren Sprache ist rekursiv aufzählbar.

(c) Die Vereinigung zweier entscheidbarer Sprachen ist entscheidbar.

(d) Die Vereinigung zweier rekursiv aufzählbarer Sprachen ist rekursiv aufzählbar.

(e) Die Schnittmenge zweier entscheidbarer Sprachen ist entscheidbar.

(f) Die Schnittmenge zweier rekursiv aufzählbarer Sprachen ist rekursiv aufzählbar.

(g) Die Schnittmenge einer rekursiv aufzählbaren Sprache und einer entscheidbaren Sprache ist rekursiv aufzählbar.

(h) Jede reguläre Sprache ist rekursiv aufzählbar.

(i) Jede Teilmenge einer regulären Sprache ist regulär.

48. Zeigen Sie:

(a) Die rekursiven Sprachen sind unter Differenz abgeschlossen. (Das heißt: Mit L_{1} und L_{2} ist auch L_{1} − L_{2} immer rekursiv.)

(b) Die rekursiv aufzählbaren Sprachen sind unter Differenz nicht abgeschlossen.

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?

59. (a) (10 Punkte) Geben Sie eine kontextfreie Grammatik für arithmetische Ausdrücke über dem Alphabet {+, ∗, (,), Z} an. Dabei sollen nur Ausdrücke ohne überflüssige Klammern erzeugt werden, d. h., solche Audrücke, die nach den üblichen mathematischen Vorrangregeln einen anderen Wert bekommen, wenn man Klammern weglässt. Zum Beispiel sind die Klammern in Z ∗ (Z + Z) notwendig, weil man den Ausdruck ohne Klammern Z∗Z+Z als (Z∗Z)+Z lesen würden. Aus diesem Grund sind auch die Klammern im Ausdruck (Z ∗ Z) + Z überflüssig (redundant).

(b) (0 Punkte)

Lösen Sie die Aufgabe mit dem erweiterten Alphabet {+, −, ∗, ÷, (,), Z}.

60. Die Grammatik

S → T | T + T | T − T
T → F | F ∗ F | F ÷ F
F → V | (S)
V → Z | ZV
Z → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

für arithmetische Ausdrücke mit konstanten ganzzahlichen Operanden ist mehrdeutig, weil zum Beispiel für den Ausdruck 3−4+5 aus der Grammatik nicht hervorgeht, ob 4 + 5 oder 3 − 4 zuerst berechnet werden soll. Die Mehrdeutigkeit wird durch die gängige Regel aufgelöst, dass Operatoren gleicher Stufe von links nach rechts ausgewertet werden.

Schreiben Sie eine äquivalente eindeutige Grammatik, die diese Regel widerspiegelt.

61. Konstruieren Sie eine kontextfreie Grammatik für die Sprache der Wörter über {0, 1}, die kein Palindrom sind:

L = { w | w ≠ w^{R} }

62. (a) Beweisen Sie, dass die Grammatik G mit den Regeln S → aS | SS | aSbS | ε genau die Wörter über {a, b} erzeugt, in denen jeder Präfix mindestens so viele a’s wie b’s enthält.

(b) Schreiben Sie ein entsprechendes Gleichungssystem für die vom der Grammatik akzeptierte Sprache L_{S} auf.

(c) L_{S} = {a, b}^{∗} ist eine Lösung dieses Gleichungssystems. Finden Sie eine Lösung, die von L(G) und {a, b}^{∗} verschieden ist.

(d) Schreiben Sie eine Grammatik ohne ε-Regeln für die Sprache L(G) − {ε}.

63. Wandeln Sie die folgende Grammatik in Chomsky-Normalform um. Prüfen Sie dann mit dem CYK-Algorithmus nach, dass das Wort a + a ∗ a ∗ a von dieser Grammatik erzeugt wird, und geben Sie einen Syntaxbaum und eine Linksableitung (für die umgewandelte Grammatik) an.

\begin{matrix}S → S ∗ A | A − A \\ A → A ∗ A | a \end{matrix}

64. (a) L_{1} sei eine kontextfreie Sprache über dem Alphabet {0, 1}, und

L_{2} = { w_{1}0w_{2}0 … w_{n}0 | w_{1}w_{2} … w_{n} ∈ L_{1}, n ≥ 0 }

sei die Sprache, wo nach jedem Buchstaben jedes Wortes eine Null eingefügt ist. Beweisen Sie, dass L_{2} ebenfalls kontextfrei ist.

(b) Lösen Sie die gleiche Aufgabe für die Sprache

L_{3} = { w_{1}0w_{2}1w_{3}0w_{4}1w_{5}0 … | w_{1}w_{2} … w_{n} ∈ L_{1}, n ≥ 0 },

wo nach jedem Buchstaben abwechselnd eine Null und eine Eins eingefügt wird.

65. Wenn man beim Beweis des Pumpinglemmas den längsten Pfad im Ableitungsbaum betrachtet, kann man die stärkere Aussage herleiten, dass es eine Zerlegung w = xyzuv mit der Längenbeschränkung |yzu| ≤ n_{0} gibt, sodass all Wörter xy^{i}zu^{i}v ∈ L sind.

66. (10 Punkte) Beweisen Sie, dass die folgenden Sprachen über dem Alphabet {a, b, c} nicht kontextfrei sind.

(a) L′_{1} = { w | w enthält doppelt so viele a’s wie b’s und doppelt so viele b’s wie c’s } (b) L_{2} = { a^{i}b^{j}c^{k} | i > j ≥ k ≥ 1 }

67. Schreiben Sie eine kontextfreie Grammatik für die regulären Ausdrücke über dem Alphabet {0, 1}. Sie können annehmen, dass die Ausdrücke voll geklammert sind, entsprechend der ursprünglichen Definition regulärer Ausdrücke, zum Beispiel

(((0 + (1)^{∗})) · ((0 + (0 · 1)) + ε))

68. Kontextfreie Sprachen sind unter Umkehrung (Spiegelung) abgeschlossen.

69. Entfernen Sie überflüssige Variablen und Regeln aus dieser Grammatik:

\begin{matrix}S → AB | CA & B → BC | AB | BDE & D → ADEba | ACA \\ A → a & C → aB | c & E → DD | BA \end{matrix}

70. (0 Punkte) Übersetzen Sie den folgenden vereinfachten Ausschnitt aus der Syntax der Programmiersprache Java aus der EBNF (extended Backus-Naur-Form) in entsprechende kontextfreie Regeln:

TryBlock ::= try Block Catches | try Block [ Catches ] finally Block Catches ::= CatchClause { CatchClause } CatchClause ::= catch ( Exception Identifier ) Block Exception ::= Identifier

Die Terminalsymbole sind hier fett gedruckt. Sie können die Variablen durch passende einbuchstabige Namen abkürzen. (Wozu dient eigentlich die Variable ”Exception“, die man doch genausogut zusammen mit der Regel ”Exception ::= Identifier“ eliminieren könnte?)

71. (a) Bleibt eine eindeutige Grammatik bei der Transformation in Chomsky-Normal-

form eindeutig?

(b) G sei eine Grammatik in Chomsky-Normalform, die eine endliche Sprache erzeugt. Finden Sie eine Schranke für das längste Wort in L(G).

(c) Wie lang kann die Ableitung eines Wortes w bei einer Grammatik in Chomsky-Normalform höchstens sein?

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

Abgabe bis Montag, 4. Juli 2005, 10:15 Uhr

72. (a) Zeigen Sie, dass die Sprache

L_{1} = { w ∈ {a, b}^{∗} | w enthält gleich viele a’s wie b’s }

deterministisch kontextfrei ist.

(b) Geben Sie eine kontextfreie Grammatik für die Sprache L_{1} an.

(c) Geben Sie eine kontextfreie Grammatik für die Sprache

L_{2} = { w | w enthält doppelt so viele a’s wie b’s }

über dem Alphabet Σ = {a, b} an.

(d) Lösen Sie dieselbe Aufgabe über dem Alphabet {a, b, c}.

73. (a) Schreiben Sie eine kontextfreie Grammatik für die durch den regulären Aus-

druck

(((0 + (1)^{∗})) · ((0 + (0 · 1)) + ε))

definierte Sprache.

(b) Wie kann man allgemein für einen regulären Ausdruck eine entsprechende kontextfreie Grammatik erzeugen?

74. (a) (6 Punkte) Wie kann man entscheiden, ob eine kontextfreie Grammatik eine

endliche Sprache erzeugt?

(b) (4 Punkte) Kann man für eine gegebene kontextfreie Grammatik G und eine durch einen endlichen Automaten gegebene reguläre Sprache L_{1} entscheiden, ob L(G) = L_{1} ist?

(c) (0 Punkte) Wie kann man für eine gegebene kontextfreie Grammatik G und eine durch einen endlichen Automaten gegebene reguläre Sprache L_{1} entscheiden, ob L(G) ⊆ L_{1} ist? (Hier müssen Sie mehrere bekannte Ergebnisse kombinieren.)

75. Das Post’sche Korrespondenzproblem und kontextfreie Sprachen.

(a) Für gegebene x_{1}, …, x_{k} ∈ Σ^{∗} ist die Sprache { a_{i_{n}}a_{i_{n−1}} … a_{i_{1}}x_{i_{1}}x_{i_{2}} … x_{i_{n}} | n ≥ 1, 1 ≤ i_{j} ≤ k } kontextfrei, wobei a_{1}, a_{2}, …, a_{k} neue Buchstaben sind, die nicht zu Σ gehören. (Versuchen Sie, mit möglichst wenigen Regeln auszukommen.)

(b) Zu jedem Post’schen Korrespondenzproblem kann man zwei kontextfreie Grammatiken G_{1} und G_{2} konstruieren, sodass das Post’schen Korrespondenzproblem genau dann eine Lösung hat, wenn L(G_{1}) ∩ L(G_{2}) ≠ ∅. Was folgt daraus für das entsprechende Entscheidungsproblem für kontextfreie Grammatiken?

76. Überprüfen Sie mit dem CYK-Algorithmus, ob das Wort w = cdccd von der folgenden Grammatik erzeugt wird, und geben Sie gegebenfalls eine Ableitung für w an.

\begin{matrix}S → AB | CD | AS & B → SB | d & D → CD | d \\ A → AS | DC & C → CA | c \end{matrix}

77. Zeigen Sie, dass die Chomsky-Hierarchie echt ist: Geben Sie eine Typ-0-Sprache an, die keine Typ-1-Sprache ist. Geben Sie eine Typ-1-Sprache an, die keine Typ-2-Sprache ist. Geben Sie eine Typ-2-Sprache an, die keine Typ-3-Sprache ist. (Und geben Sie eine Sprache an, die keine Typ-0-Sprache ist.)

78. Beschrieben Sie, wie man zu einem regulären Ausdruck einen regulären Ausdruck für die komplementäre Sprache findet.

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

freiwillige Abgabe bis Montag, 11. Juli 2005, 10:15 Uhr

79. (a) Wandeln Sie den folgenden Kellerautomaten in einen äquivalenten Kellerautomaten mit nur einem einzigen Zustand um. δ = {(q_{0}, 0, γ | q_{1}, Z_{0}γ), (q_{0}, 1, γ | q_{1}, Z_{1}γ), (q_{1}, 0, γ | q_{0}, Z_{0}γ), (q_{1}, 1, γ | q_{1}, Z_{1}Z_{1}), (q_{0}, 1, Z_{1} | q_{0}, ε), (q_{0}, 0, Z_{0} | q_{0}, ε)}. Dabei steht γ jeweils für ein beliebiges Kellersymbol γ ∈ Γ = {Z_{0}, Z_{1}}.

(b) Konstruieren Sie eine entsprechende kontextfreie Grammatik.

80. Beweisen Sie, dass die kontextfreien Sprachen abgeschlossen gegenüber der Vereinigung mit regulären Sprachen sind.

81. (a) Erweitern Sie das Haskell-Programm aus der Vorlesung zur Simulation eines deterministischen Zweiweg-Kellerautomaten und zur Berechnung der Entladefunktion^{1} so, dass es die Anzahl der Schritte ausgibt, die der Automat bis zum Leeren des Kellers macht.

(b) Erweitern Sie das Programm so, dass es auch dann terminiert, wenn der Automat in eine unendliche Schleife gerät.^{2}

82. Betrachten Sie die deterministischen Zweiweg-Kellerautomaten mit dem Eingabealphabet Σ = {a}, dem Kelleralphabet Γ = {0, 1, Z_{0}} und der Übergangsfunktion δ: Q×(Σ∪ {%, $}) × Γ → Q × Γ^{∗} × {L, N, R}.

δ(q_{0}, a, γ) = (q_{0}, 0γ, R), für γ ∈ Γ. δ(q_{0}, $, γ) = (q_{1}, γ, N), für γ ∈ Γ. δ(q_{1}, x, 1) = (q_{1}, ε, L), für x = 0 oder x = $. δ(q_{1}, x, 0) = (q_{0}, 1, N), für x = 0 oder x = $. δ(q_{1}, x, Z_{0}) = (q_{1}, ε, N), für x = 0 oder x = $.

Die übrigen Werte von δ (für x = %) sind beliebig.

(a) Beschreiben Sie das Verhalten des Automaten bei Eingabe des Wortes a^{n}, für n = 0, 1, 2, 3 und für allgemeines n.

(b) Bestimmen Sie die Entladefunktion E: Q × {0, …, n + 1} × Γ → Q × {0, …, n + 1} bei Eingabe des Wortes a^{n}.

83. (a) Beschreiben Sie formal, wie man einen nichtdeterministischen Zweiweg-Kellerauto-maten, der mit akzeptierenden Zuständen arbeitet, in einen äquivalenten Zweiweg-Kellerautomaten umwandelt, der mit leerem Keller akzeptiert.

(b) Beschreiben Sie die Transformation in die umgekehrte Richtung.

84. Mit deterministischen Zweiweg-Kellerautomaten kann man alle deterministisch kontextfreien Sprachen akzeptieren.

85. (4 Zusatzpunkte) Konstruieren Sie (a) eine Grammatik, (b) einen Kellerautomaten für die Sprache { ww^{R} | w ∈ {0, 1}^{∗} }.

86. Beweisen Sie: Wenn eine Sprache von einem deterministischen Kellerautomaten (mit akzeptierenden Zuständen) akzeptiert wird, dann gibt es eine eindeutige kontextfreie Sprache für diese Grammatik.

87. Sind die Sprachen, die von deterministischen Zweiweg-Kellerautomaten akzeptiert werden, abgeschlossen gegenüber Umkehrung (Spiegelbild)?

1http://www.inf.fu-berlin.de/lehre/SS05/GTI/2Weg-PDA-Teilwort.hs 2http://www.inf.fu-berlin.de/lehre/SS05/GTI/2Weg-PDA-Zaehler.hs

Grundlagen der theoretischen Informatik, SS 2005 Zwischenklausur, Montag, 6. Juni 2005

Aufgabe 1 2a 2b 3
Punkte 10 5 5 10 gesamt: 30

Anleitung: Bearbeiten Sie jede Aufgabe auf einem getrennten Blatt. Verwenden Sie gegebenenfalls Ergänzungsblätter. Schreiben Sie auf alle Blätter Ihren Namen und Ihre Matrikelnummer. Sie haben 90 Minuten Zeit.

Sie können alle Aussagen, die in der Vorlesung oder auf den Übungsblättern vorgekommen sind, verwenden, ohne die Beweise abzuschreiben.

Kriterium für positive Bewertung: mindestens 50 %, das sind 15 Punkte.

1. (10 Punkte) Welche dieser Aussagen sind wahr? Geben Sie einen Beweis oder ein Gegenbeispiel an.

(a) (3 Punkte) Wenn L entscheidbar ist, dann ist auch L^{∗} entscheidbar.

(b) (3 Punkte) Wenn L unentscheidbar ist, dann ist auch L^{∗} unentscheidbar.

(c) (4 Punkte) Wenn L rekursiv aufzählbar ist, dann ist auch L^{∗} rekursiv aufzählbar.

2a. (5 Punkte) Definieren Sie, was ein regulärer Ausdruck über einem Alphabet Σ ist.

2b. (5 Punkte) Was ist die kleinste Sprache L, für die

L = {0, 01} ∪ L · {000, 111}

ist? Geben Sie einen regulären Ausdruch für L an.

3. (10 Punkte) Konstruieren Sie den Minimalautomaten für die folgende Sprache L ⊂ {0, 1}^{∗}:

L = { w | w enthält eine ungerade Anzahl von Einsen, und direkt vor jeder Eins steht eine Null }

Begründen Sie in 1–2 Sätzen, warum Ihr Automat diese Sprache akzeptiert. Wenn Sie den Automaten nicht durch den Minimierungsalgorithmus konstruiert haben, dann beweisen Sie auf andere Art, dass es der Minimalautomat ist.

Grundlagen der theoretischen Informatik, SS 2005 Nachklausur zur Zwischenklausur, Montag, 4. Juli 2005

Aufgabe 1a 1b 2 3
Punkte  5 5 10 10
Punkte  gesamt:

Anleitung: Bearbeiten Sie jede Aufgabe auf einem getrennten Blatt. Verwenden Sie gegebenenfalls Ergänzungsblätter. Schreiben Sie auf alle Blätter Ihren Namen und Ihre Matrikelnummer. Sie haben 90 Minuten Zeit.

Sie können alle Aussagen, die in der Vorlesung oder auf den Übungsblättern vorgekommen sind, verwenden, ohne die Beweise abzuschreiben.

Kriterium für positive Bewertung: mindestens 50 %, das sind 15 Punkte.

1. (10 Punkte) Welche dieser Probleme sind entscheidbar? Begründen Sie Ihre Antworten, indem Sie entweder einen Lösungsalgorithmus oder einen Nichtentscheidbarkeitsbeweis in groben Zügen skizzieren.

(a) (5 Punkte) Gegeben sind zwei reguläre Ausdrücke R und S. Stellen diese beiden Ausdrücke dieselbe Sprache dar?

(b) (5 Punkte) Gegeben ist eine Turingmaschine M. Akzeptiert M alle Wörter? (also die Sprache Σ^{∗})

2. (10 Punkte) Betrachten Sie den nichtdeterministischen endlichen Automaten M mit Q = {a, b, c}, Σ = {0, 1}, Q_{0} = F = {a}, und mit

δ = {(a, 0, a), (a, 0, b), (b, 1, b), (b, 1, c), (c, 0, c), (c, 0, a)}.

Zeichnen Sie das Zustandsdiagramm, und konstruieren Sie einen dazu äquivalenten deterministischen Automaten, und den Minimalautomaten. (Der Minimalautomat ist immer ein deterministischer Automat.)

3. (10 Punkte) Konstruieren Sie einen endlichen Automaten ohne ε-Übergänge, der

die Sprache

(a + ba)^{∗}(b + ab)^{+} + (aa)^{∗}b(aaa)^{∗}

akzeptiert.

Grundlagen der theoretischen Informatik, SS 2005 Abschlussklausur

Abgabe bis Montag, 11. Juli 2005, 11:45 Uhr

Aufgabe 1 2a 2b 3
Punkte 10 5 5 10
Punkte  gesamt:

Anleitung: Bearbeiten Sie jede Aufgabe auf einem getrennten Blatt. Verwenden Sie gegebenenfalls Ergänzungsblätter. Schreiben Sie auf alle Blätter Ihren Namen und Ihre Matrikelnummer. Sie haben 90 Minuten Zeit.

Sie können alle Aussagen, die in der Vorlesung oder auf den Übungsblättern vorgekommen sind, verwenden, ohne die Beweise abzuschreiben.

Kriterium für positive Bewertung: mindestens 50 %, das sind 15 Punkte.

1. (10 Punkte) Geben Sie für die folgende kontextfreie Grammatik über dem Terminalalphabet Σ = {1, 2, 3} einen äquivalenten Kellerautomaten an. Entscheiden Sie selbst, ob der Automat deterministisch oder nichtdeterministisch ist, und wie der Automat akzeptieren soll.

\begin{matrix}S → SSS | A \\ A → A1A | AS2 | 3 \end{matrix}

2. (a) (5 Punkte) Formulieren Sie wahlweise das Pumping-Lemma für kontextfreie Sprachen oder das Pumping-Lemma für reguläre Sprachen.

(b) (5 Punkte) Beweisen Sie, dass die Sprache aller Doppelwörter

{ ww | w ∈ {0, 1}^{∗} }

nicht kontextfrei ist.

3. (10 Punkte) Wandeln Sie die Grammatik

S → aS | aAAS | B
A → Sb | aSb | ε
B → bA | AS

in Chomsky-Normalform um.

Grundlagen der theoretischen Informatik, SS 2005 Nachklausur zur Abschlussklausur

Abgabe bis Dienstag, 18. Oktober 2005, 19:30 Uhr

Aufgabe 1 2a 2b 3
Punkte 10 5 5 10
Punkte  gesamt:

Anleitung: Bearbeiten Sie jede Aufgabe auf einem getrennten Blatt. Verwenden Sie gegebenenfalls Ergänzungsblätter. Schreiben Sie auf alle Blätter Ihren Namen und Ihre Matrikelnummer. Sie haben 90 Minuten Zeit.

Sie können alle Aussagen, die in der Vorlesung oder auf den Übungsblättern vorgekommen sind, verwenden, ohne die Beweise abzuschreiben.

Kriterium für positive Bewertung: mindestens 50 %, das sind 15 Punkte.

1. (10 Punkte) Wandeln Sie die Grammatik

\begin{matrix}S → a+S | Ba \\ B → aBa | +a \end{matrix}

in Chomsky-Normalform um. Prüfen Sie dann mit dem CYK-Algorithmus nach, ob das Wort a+aa+aaa von dieser Grammatik erzeugt wird. Geben Sie gegebenenfalls einen Syntaxbaum (für die ursprüngliche Grammatik) an.

2. (a) (5 Punkte) Skizzieren Sie einen Algorithmus für das Wortproblem für Typ-1-

Sprachen. (etwa 5 Sätze)

(b) (5 Punkte) Beweisen Sie: Die Vereinigung einer kontextfreien Sprache und einer regulären Sprache ist kontextfrei.

3. Die Grammatik

\begin{matrix}S → S + S | S ∗ S | (S) | Z \\ Z → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 \end{matrix}

für einfache arithmetische Ausdrücke mit einzelnen Ziffern als Operanden ist mehrdeutig, weil zum Beispiel für den Ausdruck 3 + 4 ∗ 5 aus der Grammatik nicht hervorgeht, ob 3 + 4 oder 4 ∗ 5 zuerst berechnet werden soll.

(a) Geben Sie alle möglichen Syntaxbäume und alle möglichen Linksableitungen für das Wort 3 + 4 ∗ 5 an.

(b) Die Mehrdeutigkeit kann durch die gängige Regel aufgelöst werden, dass die Multiplikation (∗) stärker bindet als die Addition (+). Das Beispiel wird also so interpretiert, dass 3 + 4 ∗ 5 = 3 + 20 = 23 herauskommt, wenn man es ausrechnet. Schreiben Sie eine äquivalente eindeutige Grammatik, die diese Regel widerspiegelt.