Übung zur Vorlesung

Theoretische Informatik I

Prof. Christoph Kreitz / Jens Otten Universität Potsdam, Theoretische Informatik — Sommersemester 2004 Blatt 9 — Abgabetermin: 26. Juni 2004, 11.00 Uhr

Quiz 9

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

[ ] Mit Hilfe des Pumping-Lemmas kann gezeigt werden, dass eine Sprache nicht als regulärer Ausdruck dargestellt werden kann.

[ ] Aus dem Pumping-Lemma folgt, dass jedes genügend große Wort einer regulären Sprache in der Form xy^{i}z dargestellt werden kann (für feste x, y, z∈Σ^{∗}).

[ ] Bei der Anwendung des Pumping-Lemmas auf eine Sprache L, lässt sich die Konstante n stets so wählen, dass n nicht größer ist als die Anzahl der Zustände des kleinsten NEA A mit L=L(A).

[ ] Jede kontextfreie Grammatik hat nur Produktionsregeln der Form A→s oder A→ϵ mit A∈V und s∈(V ∪T)^{∗}

[ ] Durch Ableitungsbäume können alle Wörter einer kontextfreien Grammatik dar- gestellt werden.

Aufgabe 9.1 (Pumping Lemma für reguläre Sprachen)

Beweisen Sie, dass die folgenden Sprachen keine regulären Sprachen sind.

1. L_{1}={0^{i}1^{3i} | i∈IN}.

2. L_{2}={0^{i^{2}} | i∈IN}.

Aufgabe 9.2 (Kontextfreie Grammatiken, Ableitungsbäume)

Sei T ={0, 1, (,), +,^{∗}, ∅, e} die Menge der Symbole, die in regulären Ausdrücken über dem Alphabet {0, 1} verwendet werden. Dabei steht e für das leere Wort ϵ.

1. Geben Sie eine kontextfreie Grammatik über der Menge der Terminalsymbole T an, die genau die regulären Ausdrücke über dem Alphabet {0, 1} erzeugt.

2. Geben Sie eine linksseitige Ableitung und eine rechtsseitige Ableitung für den Ausdruck (1+e)^{∗}01 an. Geben Sie außerdem einen Ableitungsbaum für diesen Ausdruck an.

Übung zur Vorlesung Theoretische Informatik I Blatt 9

Aufgabe 9.3 (Pumping Lemma für reguläre Sprachen) [3 Punkte]

Beweisen Sie, dass die folgenden Sprachen keine regulären Sprachen sind.

1. L_{1}={0^{i^{3}} | i∈IN}.

2. L_{2}={ww | w∈{a, b}^{∗}}.

Aufgabe 9.4 (Kontextfreie Grammatiken, Ableitungsbäume) [3 Punkte]

Die Sprache der aussagenlogischen Formeln besteht aus den Symbolen T ={A, B, C, a, b, c, (,), ∧, ∨, ⇒, ¬}, wobei Aussagenvariablen mit einem Großbuchstaben (A, B oder C) beginnen, dem eine Kombination aus weiteren Kleinbuchstaben (a, b oder c) folgen können.

1. Geben Sie eine kontextfreie Grammatik über der Menge der Terminalsymbole T an, die genau die oben beschriebenen aussagenlogischen Formeln erzeugt.

2. Geben Sie eine linksseitige Ableitung und eine rechtsseitige Ableitung für den Ausdruck

(A ∧ (A ⇒ Bac)) ∨ C ⇒ (¬C ⇒ Bac)

an. Geben Sie außerdem einen Ableitungsbaum für diesen Ausdruck an.

Aufgabe 9.5 (Kontextfreie Grammatiken) [3 Punkte]

1. Geben Sie eine kontextfreie Grammatik für die Sprache L={w∈{0, 1}^{∗} | w enthält doppelt so viele Nullen wie Einsen} an.

2. Zeigen Sie, dass nicht jede kontextfreie Sprache, die ϵ nicht enthält, durch eine Grammatik erzeugt werden kann, deren Produktionsregeln die Form A→BCD oder A→a haben (mit A, B, C, D∈V und a∈T).

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.