Übung zur Vorlesung

Theoretische Informatik I

Prof. Christoph Kreitz / Jens Otten Universität Potsdam, Theoretische Informatik — Sommersemester 2004 Blatt 4 — Abgabetermin: 15. Mai 2004, 11.00 Uhr

Quiz 4

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

[ ] ϵ-NEA sind NEAs, die zwei zusätzliche Übergänge für das leere Wort und für ϵ haben.

[ ] Die ϵ-Hülle eines Zustandes q enthält sowohl q als auch alle Zustände, die sich von q aus mit einer beliebigen Anzahl von ϵ-Übergängen erreichen lassen.

[ ] Für einen ϵ-NEA (Q, Σ, δ, q_{0}, F), der nur ϵ -Übergänge zwischen Zuständen be- sitzt, gilt: ϵ-Hülle(q_{0})=Q.

[ ] Einen DEA kann man sich als Spezialfall eines NEA vorstellen. [ ] Einen ϵ-NEA kann man sich als Spezialfall eines NEA vorstellen.

Aufgabe 4.1 (ϵ-NEA: Umwandlung ϵ-NEA in DEA)

Gegeben sei ein ϵ-NEA A=({p, q, r}, {a, b, c}, δ, p, {r}) wobei die Übgergangsfunktion δ durch die folgende Übergangstabelle definiert ist.

ϵ a b c
→ p ∅ {p} {q} {r}
q {p} {q} {r} ∅
∗r {q} {r} ∅ {p}

1. Geben Sie das Übergangsdiagramm für diesen Automaten an.

2. Berechnen Sie die ϵ-Hülle für jeden Zustand q′∈{p, q, r}.

3. Geben Sie alle Zeichenreihen mit einer Länge von zwei oder weniger Zeichen an, die von dem Automaten akzeptiert werden.

4. Wandeln Sie den Automaten in einen DEA um. Benutzen Sie hierbei die optimierte Teilmengenkonstruktion.

Aufgabe 4.2 (ϵ-NEA: Umwandlung NEA in ϵ-NEA)

Zeigen Sie, dass ein NEA A=(Q, Σ, δ, q_{0}, F) in einen ϵ-NEA A′=(Q′, Σ, δ′, q′_{0}, F′) umgewandelt werden kann, der dieselbe Sprache wie A akzeptiert.

Tipp: Es bleibt zu zeigen, wie δ′ aus δ konstruiert werden kann, so dass δ̂′(q_{0}, w) = δ̂(q_{0}, w) für alle w∈Σ^{∗}.

Übung zur Vorlesung Theoretische Informatik I Blatt 1

Aufgabe 4.3 (ϵ-NEA: Umwandlung ϵ-NEA in DEA) [3 Punkte]

Gegeben sei ein ϵ-NEA A=({p, q, r, s}, {a, b, c, d}, δ, p, {s}) wobei die Übgergangsfunktion δ durch das folgende Übergangsdiagramm definiert ist.

[figure: a; ϵ; d; b; c; ϵ; b; c; s; r; q; p; Start]

1. Geben Sie die Übergangstabelle für diesen Automaten an.

2. Berechnen Sie die ϵ-Hülle für jeden Zustand q′∈{p, q, r, s}.

3. Geben Sie alle Zeichenreihen mit einer Länge von zwei oder weniger Zeichen an, die von dem Automaten akzeptiert werden.

4. Wandeln Sie den Automaten in einen DEA um. Benutzen Sie hierbei die optimierte Teilmengenkonstruktion.

Aufgabe 4.4 (ϵ-NEA: Umwandlung ϵ-NEA in NEA) [3 Punkte]

In Aufgabe 4.2 wurde gezeigt, dass für jeden NEA A ein äquivalenter ϵ-NEA A′ konstruiert werden kann, der dieselbe Sprache wie A akzeptiert. Um zu zeigen, dass NEAs und ϵ-NEAs die gleiche Menge von Sprachen akzeptieren, muss noch die Gegenrichtung bewiesen werden.

Beschreiben Sie, wie ein gegebener ϵ-NEA A′ in einen NEA A umgewandelt werden kann, so dass A′ und A diesselbe Sprache akzeptieren. Führen Sie diese Umwandlung am Beispiel des Automaten in Aufgabe 4.3 durch.

Aufgabe 4.5 (Konstruktion eines ϵ-NEA) [3 Punkte]

Sei L_{bc} eine Sprache, die alle Wörter aus {a, b, c}^{∗} enthält, die unter den letzten vier Zeichen mindestens ein b oder ein c enthalten.

Konstruieren Sie einen ϵ-NEA A, der die Sprache L_{bc} akzeptiert. Ihr Automat A darf maximal fünf Zustände haben. Von jedem Zustand aus und auf jeden Zustand darf es maximal zwei Übergänge für ein und dasselbe Eingabesymbol geben.

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.