Übung zur Vorlesung

Theoretische Informatik I

Prof. Christoph Kreitz / Jens Otten Universität Potsdam, Theoretische Informatik — Sommersemester 2004

Blatt 12 — Abgabetermin (nur für Studenten mit weniger als 49 Hausaufgaben-Punkte): 14. Juli 2004, 16.00 Uhr

Quiz 12

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

[ ] Falls L_{1} und L_{2} kontextfreie Sprachen sind, dann ist auch \overline{L_{1} ∩ L_{2}} eine kontext- freie Sprache.

[ ] Falls L_{1} und L_{2} kontextfreie Sprachen sind, dann ist auch \overline{\overline{L_{1}} ∩ \overline{L_{2}}} eine kontext- freie Sprache.

[ ] Jede kontextfreie Sprache L kann in Chomsky-Normalform transformiert wer- den, bei der lediglich Regeln der Form A→BC und A→a (mit A, B, C∈V, a∈T) benutzt werden.

[ ] Sei G=({A, B, S}, {a, b, c}, P, S) ein Grammatik mit den Produktionsregeln P ={S→AB|a, A→b}. Dann sind alle Symbole von G erzeugend und erreichbar.

[ ] Sei G=({A, B, S}, {a, b, c}, P, S) ein Grammatik mit den Produktionsregeln P ={S→AB, A→aAA|ϵ, B→bBB|ϵ}. Dann sind alle Variablen von G eliminier- bar.

Aufgabe 12.1 (Pumping-Lemma) Geben Sie für jede der folgenden Sprachen L entweder einen endlichen Automaten an, oder zeigen Sie mit Hilfe des Pumping-Lemmas, dass L nicht regulär ist.

1. L={a^{n}b^{m} | n, m∈IN_{0} und n≥m}.

2. L={1^{n}0^{m} | n, m∈IN_{0} und n+m ist gerade}.

3. L={w∈{a, b}^{∗} | w enthält gleich viele as und bs}.

Aufgabe 12.2 (Grammatiken)

1. Konstruieren Sie eine linkslineare Grammatik G = (V, T, P, S) für die Sprache L = {w∈{a, b, c}^{∗} | w=cvc mit v∈{a, b}^{∗} und hinter jedem a in v folgt bb}.

2. Geben Sie eine Grammatik G=(V, T, P, S) für die Sprache L={a^{n}b^{2n}a^{n} | n∈IN_{0}} an.

Übung zur Vorlesung Theoretische Informatik I Blatt 12

Aufgabe 12.3 (Minimierung endlicher Automaten) [3 Bonus-Punkte]

Gegeben sei der durch die folgende Übergangstabelle definierte endliche Automat.

a b
q_{1} q_{2} q_{5}
q_{2} q_{7} q_{3}
∗q_{3} q_{4} q_{7}
q_{4} q_{2} q_{5}
→q_{5} q_{7} q_{3}
q_{6} q_{3} q_{5}
q_{7} q_{1} q_{3}

1. Entfernen Sie die unerreichbaren Zustände aus dem Automaten.

2. Ermitteln Sie mit Hilfe des Table-filling Verfahrens alle Paare äquivalenter Zustände.

3. Geben Sie einen äquivalenten minimalen DEA an.

Aufgabe 12.4 (Kontextfreie Grammatiken) [3 Bonus-Punkte]

Sei L={w∈{+, −, ∗, /, (,), 0, 1}^{∗} | w ist ein arithmetischer Ausdruck über {0, 1}}.

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

2. Geben Sie zwei unterschiedliche Ableitungsbäume für 1 + 10 ∗ 11 an.

3. Geben Sie eine eindeutige Grammatik für L an.

Aufgabe 12.5 (Pushdown-Automaten) [3 Bonus-Punkte]

Sei L={a^{n}b^{m}c^{m′}d^{n′} | n, m∈IN_{0} und n≥n′, m≥m′}. Konstruieren Sie einen nichtdeterministischen Pushdown-Automaten P =(Q, Σ, Γ, δ, q_{0}, Z_{0}, F) mit L(P)=L.

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.