Übung zur Vorlesung

Theoretische Informatik I

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

Quiz 6

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

[ ] Die Umwandlung in einen regulären Ausdruck durch Zustandselimination funk- tioniert auch bei NEAs mit ϵ-Übergängen.

[ ] Falls ein NEA A=(Q, Σ, δ, q_{0}, F) die Sprache L akzeptiert, so akzeptiert der NEA A′=(Q, Σ, δ, q_{0}, Q\F) die komplementäre Sprache L̄:={w∈Σ^{∗} | w∉L}.

[ ] Bei der Umwandlung durch Pfadanalyse wachsen die entstehenden regulären Aus- drücke R_{ij}^{(k)} quadratisch mit der Anzahl der Zustände des Automaten.

[ ] Falls RS=T R^{∗} für gegebene reguläre Ausdrücke R, S, T, dann ist S=T^{∗}. [ ] Jeder endlicher Automat (DEA, NEA, ϵ-NEA) lässt sich in einen äquivalenten regulären Ausdruck umwandeln.

Aufgabe 6.1 (Umwandlung endlicher Automaten in reguläre Ausdrücke)

Gegeben sei ein DEA A=({q_{1}, q_{2}, q_{3}}, {a, b}, δ, q_{1}, {q_{3}}), wobei die Übergangsfunktion δ durch die folgende Tabelle gegeben ist.

\begin{aligned}& a & b \\ → q_{1} & q_{2} & q_{1} \\ q_{2} & q_{3} & q_{1} \\ ∗q_{3} & q_{3} & q_{2} \end{aligned}

1. Wandeln Sie den Automaten mit Hilfe der Pfadanalyse in einen äquivalenten regulären Ausdruck um. Stellen Sie sich den Zustand q_{i} so vor, als handle es sich um den Zustand mit der Nummer i. Formulieren Sie nacheinander alle Ausdrücke R_{ij}^{(0)}, R_{ij}^{(1)} und R_{ij}^{(2)} für 1≤i, j≤3. Vereinfachen Sie die resultierenden Ausdrücke. Geben Sie dann einen regulären Ausdruck für R_{13}^{(3)} an, d.h. für die Sprache, die der Automat akzeptiert.

2. Wandeln Sie den Automaten in einen regulären Ausdruck um, indem Sie den Zustand q_{2} eliminieren.

Aufgabe 6.2 (Umwandlung in reguläre Ausdrücke durch Zustandselimination)

Gegeben sei ein DEA A=({q_{1}, q_{2}, q_{3}, q_{4}}, {a, b}, δ, q_{1}, {q_{1}}), wobei die Übergangsfunktion δ durch die folgende Tabelle gegeben ist.

a b
→ ∗q_{1} q_{4} q_{1}
q_{2} q_{1} q_{4}
q_{3} q_{3} q_{2}
q_{4} q_{2} q_{3}

Wandeln Sie diesen Automaten durch die Technik der Zustandselimination schrittweise in einen regulären Ausdruck um.

Übung zur Vorlesung Theoretische Informatik I Blatt 6

Aufgabe 6.3 (Umwandlung in reguläre Ausdrücke durch Pfadanalyse) [3 Punkte]

Gegeben sei ein NEA A=({q_{1}, q_{2}, q_{3}}, {a, b, c}, δ, q_{1}, {q_{3}}), wobei die Übergangsfunktion δ durch die folgende Tabelle gegeben ist.

a b c
→ q_{1} q_{2} ∅ ∅
q_{2} q_{1} q_{3} q_{2}
∗q_{3} ∅ q_{2} ∅

Wandeln Sie den Automaten mit Hilfe der Pfadanalyse in einen äquivalenten regulären Ausdruck um. Stellen Sie sich den Zustand q_{i} so vor, als handle es sich um den Zustand mit der Nummer i. Formulieren Sie nacheinander alle Ausdrücke R_{ij}^{(0)}, R_{ij}^{(1)} und R_{ij}^{(2)} für 1≤i, j≤3. Vereinfachen Sie die resultierenden Ausdrücke. Geben Sie dann einen regulären Ausdruck für R_{13}^{(3)} an, d.h. für die Sprache, die der Automat akzeptiert.

Aufgabe 6.4 (Umwandlung in reg. Ausdrücke durch Zustandselimination) [3 Punkte]

Betrachten Sie den in Aufgabe 6.3 angegebenen Automaten.

1. Wandeln Sie den Automaten in einen regulären Ausdruck um, indem Sie den Zustand q_{2} eliminieren.

2. Beschreiben Sie, welche Sprache dieser Automat akzeptiert. Geben Sie außerdem einen möglichst kurzen regulären Ausdruck für diese Sprache an.

Aufgabe 6.5 (Umwandlung durch Zustandselimination) [3 Punkte]

Gegeben sei der (allseits bekannte) NEA A_{rad}= {{q_{0}, q_{1}, q_{2}, q_{3}, q_{4}}, {r, a, d}, δ_{rad}, q_{0}, {q_{1}, q_{3}, q_{4}}}, wobei die Zustandsübergangsfunktion δ_{rad} durch folgendes Diagramm gegeben ist.

[figure: d, r; d, r; d, r; a; a; a; r, a, d; Start; r; d; a; q_{4}; q_{3}; q_{2}; q_{1}; q_{0}]

Wandeln Sie diesen Automaten durch die Technik der Zustandselimination schrittweise in einen regulären Ausdruck um. Vereinfachen Sie dabei keine Ausdrücke (d.h. kein Ausklammern, kein Anwenden von Distributivgesetzen, etc.).

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.