Übung zur Vorlesung

Theoretische Informatik I

Prof. Christoph Kreitz / Jens Otten Universität Potsdam, Theoretische Informatik — Sommersemester 2004 Blatt 10 — Abgabetermin: 03. Juli 2004, 11.00 Uhr

Quiz 10

Markieren Sie die nachfolgenden Aussagen als ”wahr” oder ”falsch”.

[ ] Sei L eine reguläre/kontextfreie Sprache und L′⊂L. Dann ist auch L′ eine re- guläre/kontextfreie Sprache.

[ ] Falls G eine mehrdeutige Grammatik ist, dann ist L(G) eine mehrdeutige Sprache.

[ ] Sei P =(Q, Σ, Γ, δ, q_{0}, Z_{0}, F) ein Pushdown-Automat, der die Sprache L akzeptiert und dabei nur einen Stack der festen Größe k∈IN benutzt. Dann ist die Sprache L regulär.

[ ] Ein Pushdown-Automat, der genau dann eine Sprache L akzeptiert, wenn der Stack leer ist, akzeptiert genau die kontextfreien Sprachen.

[ ] Sei P ein Pushdown-Automat mit (q, x, α) ⊢^{∗} (p, y, β). Dann gilt für alle w∈Σ^{∗}, γ∈Γ^{∗}, dass (q, xw, αγ) ⊢^{∗} (p, yw, βγ).

Aufgabe 10.1 (Mehrdeutigkeit von Grammatiken)

Sei G = ({S}, {0, 1, (,), +}, P, S} eine Grammatik mit den Produktionsregeln P = {S→0, S→1, S→SS, S→S+S, S→(S)}, die als Sprache eine Untermenge der regulären Ausdrücke erzeugt.

1. Geben Sie zwei unterschiedliche Ableitungsbäume für das Wort 0+10 an.

2. Geben Sie zwei unterschiedliche linksseitige Ableitungen für das Wort 1+0+1 an.

3. Geben Sie eine Grammatik G′ für die Sprache L(G) an, die nicht mehrdeutig ist. Tipp: Untersuchen Sie, wie das Problem der Mehrdeutigkeit der Grammatik für die Sprache der Ausdrücke über + und * gelöst wurde.

Aufgabe 10.2 (Pushdown-Automaten)

1. Sei P =({q_{0}, q_{1}, q_{2}}, {a, b, c}, {X, Z_{0}}, δ, q_{0}, Z_{0}, {q_{2}}) mit der Übergangsfunktion δ definiert durch folgendes Übergangsdiagramm.

[figure: Start; ϵ, Z_{0}/Z_{0}; ϵ, X/X; ϵ, Z_{0}/Z_{0}; c, X/ϵ; b, X/XX; a, X/XX; b, Z_{0}/XZ_{0}; a, Z_{0}/XZ_{0}; q_{2}; q_{1}; q_{0}]

Geben Sie eine Ableitung (eine Folge von Konfigurationen) für das Wort abaccc an. Geben Sie außerdem die von dem Automaten akzeptierte Sprache L(P) an.

2. Geben Sie einen Pushdown-Automaten für die Sprache L={w∈{0, 1}^{∗} | w enthält die gleiche Anzahl von Nullen und Einsen} an.

Übung zur Vorlesung Theoretische Informatik I Blatt 10

Aufgabe 10.3 (Mehrdeutigkeit von Grammatiken) [3 Punkte]

Die Sprache der aussagenlogischen Formeln besteht aus den Symbolen T ={A, B, C, (,), ∧, ∨, ⇒, ¬}, wobei Aussagenvariablen aus einem Großbuchstaben (A, B oder C) bestehen.

1. Geben Sie eine mehrdeutige kontextfreie Grammatik G für die Sprache der aussagenlogischen Formeln über T an.

2. Zeigen Sie, dass Ihre Grammatik G mehrdeutig ist, indem Sie zwei unterschiedliche Ableitungsbäume für ein Wort aus L(G) angeben.

3. Geben Sie eine eindeutige Grammatik G′ an, mit L(G)=L(G′). Gehen sie davon aus, dass ¬ stärker bindet als ∧, welches wiederum stärker bindet als ∨, welches stärker bindet als ⇒. ∧, ∨ und ⇒ sollen als linksassoziativ behandelt werden.

Aufgabe 10.4 (Pushdown-Automaten) [3 Punkte]

Sei L={a^{n}b^{n+m}c^{m} | n, m∈IN}.

1. Geben Sie eine kontextfreie Grammatik G=(V, T, P, S) für diese Sprache an.

2. Geben Sie einen Pushdown-Automaten P =(Q, Σ, Γ, δ, q_{0}, Z_{0}, F) für diese Sprache an.

3. Geben Sie eine Ableitung (eine Folge von Konfigurationen) des Automaten P für das Wort aabbbc an.

Aufgabe 10.5 (Kontextfreie versus reguläre Sprachen) [3 Punkte]

1. Zeigen Sie, dass ein Pushdown-Automat mit einem Stack der festen Größe k, genau die regulären Sprachen akzeptiert.

Tipp: Zeigen Sie, wie ein Pushdown-Automat mit einem Stack der Größe k in einen äquivalenten nichtdeterministischen endlichen Automaten umgewandelt werden kann und umgekehrt.

2. Zeigen Sie mit Hilfe des Pumping-Lemmas, dass die folgende Sprache nicht regulär ist: L={0^{i}1^{j} | ggT (i, j)=1}.

Haben Sie Fragen, Anregungen oder Probleme? Lassen Sie es uns wissen!

• Prof. Christoph Kreitz, Raum 1.18, kreitz@cs.uni-potsdam.de, Tel. 0331/977 3060 Sprechstunde: immer, wenn die Türe des Raumes 1.18 offen steht, und am Mittwoch 11.00 bis 12.30 Uhr

• Jens Otten, Raum 1.20, jeotten@cs.uni-potsdam.de, Tel. 0331/977 3072 Sprechstunde: immer, wenn die Türe des Raumes 1.20 offen steht, und am Dienstag 14.00 bis 16.00 Uhr.