Übung zur Vorlesung

Theoretische Informatik I

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

Quiz 3

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

[ ] Die Worte ”web”, ”ebay” und ”Zylinderkopfdichtung” können nur von nichtde- terministischen endlichen Automaten (NEA) akzeptiert werden.

[ ] Die Übergangsfunktion eines NEA ordnet jedem Paar (q, a) mit q∈Q, a∈Σ eine Teilmenge von Q zu, die auch leer sein kann.

[ ] Sei A=(Q, Σ, δ, q_{0}, F) ein NEA mit δ̂(q_{0}, w)={q_{2}, q_{3}}. Das Wort w wird genau dann von A akzeptiert, wenn {q_{2}, q_{3}}⊆F.

[ ] Jeder NEA mit n Zuständen kann in einen deterministischen endlichen Auto- maten (DEA) mit maximal n^{2} vielen Zuständen überführt werden, der dieselbe Sprache akzeptiert.

[ ] Die erste Aussage von Quiz 3 kann durch ein Gegenbeispiel widerlegt werden.

Aufgabe 3.1 (NEA: Umwandlung NEA in DEA)

Sei L_{abba} eine Sprache, die alle Wörter aus {a, b, c}^{∗} enthält, die das Wort abba enthalten.

1. Geben Sie einen nichtdeterministischen endlichen Automaten A=(Q, Σ, δ, q_{0}, F) an, der die Sprache L_{abba} akzeptiert. Geben Sie sowohl das Übergangsdiagramm als auch die Übergangstabelle für δ an.

2. Wandeln Sie Ihren nichtdeterministischen Automaten A in einen deterministischen Automaten A′=(Q′, Σ′, δ′, q′_{0}, F′) um, der dieselbe Sprache wie A akzeptiert. Benutzen Sie die (iterative) optimierte Teilmengenkonstruktion zur Berechnung der neuen Zustandsmenge Q′.

3. Wieviele Elemente hätte die Potenzmenge P(Q) der Zustandsmenge Q?

Aufgabe 3.2 (NEA: Simultane Induktion)

Gegeben sei der durch das folgende Übergangsdiagramm definierte nichtdeterministische Automat A, für ein beliebiges aber festes n∈IN, n≥1.

[figure: 0,1; ...; 0,1; 0,1; 0,1; 0,1; 1; Start; q_{n−1}; q_{n}; q_{2}; q_{1}; q_{0}]

Beweisen Sie, dass dieser Automat die folgende Sprache akzeptiert:

L(A)={w∈{0, 1}^{∗} | das n-te Zeichen vor dem Ende von w ist eine 1}.

Tipp: Zeigen Sie durch simultane (strukturelle) Induktion über w, dass sich der Automat nach dem Lesen der Eingabefolge w im Zustand q_{i} befindet, d.h q_{i}∈δ̂(q_{0}, w) für i≥1 genau dann, wenn das i-te Zeichen vor dem Ende von w eine 1 ist.

Übung zur Vorlesung Theoretische Informatik I Blatt 1

Aufgabe 3.3 (NEA: Textanalyse) [3 Punkte]

Sei L={w∈{a, b, c, d}^{∗} | w=vabc oder w=vbc oder w=vca für ein v∈{a, b, c, d}^{∗}}.

1. Enwerfen Sie einen nichtdeterministischen endlichen Automaten A = (Q, Σ, δ, q_{0}, F), der die Sprache L(A) akzeptiert.

2. Wandeln Sie Ihren nichtdeterministischen Automaten A in einen deterministischen Automaten A′=(Q′, Σ′, δ′, q′_{0}, F′) um, der dieselbe Sprache wie A akzeptiert. Benutzen Sie die (iterative) optimierte Teilmengenkonstruktion zur Berechnung von Q′.

Aufgabe 3.4 (NEA: Umwandlung DEA in NEA) [3 Punkte]

In der Vorlesung wurde gezeigt, dass für jeden nichtdeterministischen Automaten (NEA) A ein äquivalenter deterministischer Automat (DEA) A′ konstruiert werden kann, der dieselbe Sprache wie A akzeptiert. Um zu zeigen, dass NEAs und DEAs die gleiche Menge von Sprachen akzeptieren, muss noch die Gegenrichtung bewiesen werden.

Zeigen Sie: Wenn eine Sprache L von einem DEA A′ akzeptiert wird, dann gibt es auch einen NEA A, der L akzeptiert.

Tipp: Sei A′=(Q′, Σ′, δ′, q_{0}, F′) ein DEA. Dann kann ein äquivalenter NEA A=(Q, Σ, δ, {q_{0}}, F) konstruiert werden mit δ(q, a)={p}, wenn δ′(q, a)=p. Zeigen Sie durch (strukturelle) Induktion über w, wenn δ̂′(q_{0}, w)=p, dann δ̂(q_{0}, w)={p}. Geben Sie auch die Mengen Q, Σ und F an, und zeigen Sie dass w genau dann von A akzeptiert wird, wenn w von A′ akzeptiert wird.

Aufgabe 3.5 (NEA: Simultane Induktion) [3 Punkte]

Sei L_{000} eine Sprache, die alle Wörter in {0, 1}^{∗} enthält, bei denen die Anzahl der vorkommenden Nullen ein Vielfaches von drei ist.

1. Geben Sie einen deterministischen oder nichtdeterministischen endlichen Automaten A mit maximal drei Zuständen an, der die Sprache L_{000} akzeptiert. Beachten Sie, dass Null ein Vielfaches von drei ist.

2. Beweisen Sie, dass der von Ihnen entwickelte Automat A die Sprache L_{000} akzeptiert.

Tipp: Geben Sie an welche Form eine Eingabe w hat, wenn sich der Automat im Zustand q_{i} befindet. Beweisen Sie dann durch simultane Induktion über w die Richtigkeit Ihrer Aussagen.

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.