Übung zur Vorlesung

Theoretische Informatik I

Prof. Christoph Kreitz / Jens Otten Universität Potsdam, Theoretische Informatik — Sommersemester 2004 Blatt 2 — Abgabetermin: 30. April 2004, 11.00 Uhr

Quiz 2

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

[ ] Ein Beweis ist ein Argument, das nur mich und meinen Freund/in überzeugen muss.

[ ] Der Diagonalisierungsbeweis zur Unentscheidbarkeit der Terminierung von belie- bigen Programmen ist ein Widerspruchsbeweis.

[ ] Es gibt Programme, deren Terminierung bewiesen werden kann. [ ] Die vollständige Induktion ist ein Spezialfall der strukturellen Induktion (über den natürlichen Zahlen) und enthält immer einen Induktionsanfang.

[ ] Ein endlicher Automat kann nur endliche Sprachen erkennen.

Aufgabe 2.1 (Deterministische endliche Automaten)

Die nachfolgende Abbildung zeigt ein Spiel, in dem Murmeln bei A oder B in die Spielbahn gefallen lassen werden. Je nach Stellung der Hebel H_{1} und H_{2} rollen die Murmeln in der Spielbahn nach links oder rechts. Sobald eine Murmel auf einen dieser Hebel trifft, wird der Hebel nach dem Passieren der Murmel umgestellt, so dass die nächste Murmel in die andere Richtung rollt.

[figure: H_{2}; H_{1}; D; C; B; A]

1. Modellieren Sie dieses Spiel als endlichen Automaten A_{Murmel}, der als Eingabe eine Zeichenreihe aus den Buchstaben a und b erhält. Diese Eingaben entsprechen dem Fallenlassen von Murmeln bei A oder B. Wenn die (letzte) Murmel durch die Öffnung D aus dem Spiel rollt, dann soll der Automat einen akzeptierenden Zustand einnehmen, andernfalls einen nicht akzeptierenden Zustand. Der Startzustand soll dem Zustand in der Abbildung entsprechen. Geben Sie das Übergangsdiagramm für diesen Automaten an.

2. Geben Sie den endlichen Automaten als Tupel A_{Murmel}={Q, Σ, δ, q_{0}, F } an, wobei die Funktion δ als Übergangstabelle dargestellt werden soll.

3. Geben Sie die Sprache L(A_{Murmel}) des Automaten A_{Murmel} an.

Übung zur Vorlesung Theoretische Informatik I Blatt 1

Aufgabe 2.2 (Deterministische endliche Automaten)

Gegeben sei eine Sprache L_{abc} die genau alle Wörter aus {a, b, c}^{∗} enthält, die auf abc enden und deren Länge ein Vielfaches von 3 ist, d.h. L_{abc}={w∈{a, b, c}^{∗} | ∃v∈{a, b, c}^{∗} : w=vabc und |w| mod 3 = 0}.

Geben Sie einen Automaten A_{abc}=(Q, Σ, δ, q_{0}, F) an, der die Sprache L_{abc} akzeptiert. Die Funktion δ kann als Übergangsdiagramm oder Übergangstabelle angegeben werden.

Aufgabe 2.3 (Deterministische endliche Automaten) [3 Punkte]

Geben Sie die Sprache L_{rad} an, die der endliche Automat A_{rad}={{q_{0}, q_{1}, q_{2}, q_{3}, q_{4}}, {r, a, d}, δ_{rad}, q_{0}, {q_{1}, q_{3}, q_{4}}} akzeptiert, 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}]

Aufgabe 2.4 (Induktive Beweise: Strukturelle Induktion) [3 Punkte]

Ein binärer Baum sei rekursiv wie folgt definiert:

(1) Ein Knoten N ist ein binärer Baum; N ist gleichzeitig die Wurzel des Baumes.

(2) Falls T_{1} und T_{2} binäre Bäume sind, dann ist auch die folgende Konstruktion ein binärer Baum, bei dem ein neuer Knoten (die neue Wurzel) N mit den Wurzeln der Bäume T_{1} und T_{2} durch Kanten verbunden wird.

Beweisen Sie mit der strukturellen Induktion, d.h. über den rekursiven Aufbau von binären Bäumen, die folgende Aussage: Ein binärer Baum T mit n inneren Knoten besitzt insgesamt genau 2n+1 Knoten. (Ein innerer Knoten ist ein Knoten mit mehr als einer Kante.)

Aufgabe 2.5 (Deterministische endliche Automaten) [3 Punkte]

Geben Sie das Übergangsdiagramm eines (deterministischen) endlichen Automaten an, der alle Wörter über dem Alphabet {0, 1} akzeptiert, die, wenn sie in umgekehrter Reihenfolge als Binärdarstellung einer ganzen Zahl interpretiert werden, durch 3 teilbar sind.

Tipp: Schauen Sie sich die Wertigkeit der einzelnen Ziffern in der Binärdarstellung an und benutzen Sie die Restklassen modulo 3 für die Modellierung der Zustände.

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.