Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl:

Kennwort: Herbst 461 1 3

Arbeitsplatz-Nr.: 2008

Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen

— Prüfungsaufgaben —
Fach: Informatik (Unterrichtsfach)
Einzelprüfung: Theoretische Informatik

Anzahl der gestellten Themen (Aufgaben): 2
Anzahl der Druckseiten dieser Vorlage: E

Thema Nr. 1

Aufgabe

Ein Bauer will mit einem Wolf, einer Ziege und einem Kohlkopf einen Fluss überqueren. Das Boot ist
klein, so dass er auf einer Überfahrt jeweils nur eines der Tiere oder den Kohlkopf mitnehmen kann.
Ohne die Aufsicht des Bauern verschlänge der Wolf die Ziege und die Ziege fräße den Kohlkopf.

Modellieren Sie das Problem durch einen endlichen Automaten, der nur die Lösungen akzeptiert. Die
Zustände beschreiben die Situationen auf beiden Seiten des Flusses, z. B. die Anfangssituation

„{ BZWK}- {}, wobei B den Bauern, W den Wolf, Z die Ziege, K den Kohlkopf und - den Fluss
bezeichne. Die Eingaben stellen die Überfahrten dar; b, bw, bz, bk bezeichnen die Überfahrten des
Bauern allein, mit dem Wolf, mit der Ziege, dem Kohlkopf.

Fortsetzung nächste Seite!
Herbst 2008 Einzelprüfungsnummer 46113 Seite 2

Aufgabe 2

Gegeben ist die Grammatik G mit der Variablen S, dem Startzeichen S, den Terminalzeichen a, b und
c sowie Regeln

S — aS|SalbSb|c
a) Geben Sie die Sprache L(G) in Mengenschreibweise an.
b) Bringen Sie G in Chomsky-Normalform.
c) Überprüfen Sie mit Hilfe des CYK-Algorithmus, ob das Wort abacab in der Sprache L(G) liegt.
Geben Sie die Tabelle an.
Aufgabe 3
a) Definieren Sie das Halteproblem für Turing-Maschinen als Sprache H über dem Alphabet {0,1,#}.
b) Gegeben sei das folgende Problem E:

Entscheiden Sie, ob die deterministische Turing-Maschine codiert durch n auf
genau den Eingaben 10 und 01 hält.

Zeigen Sie, dass E nicht entscheidbar ist. Benutzen Sie, dass H aus a) nicht entscheidbar ist.

c) Angenommen, es wurde gezeigt, dass P = NP ist. Zeigen Sie, dass dann jede Sprache LeP sogar
NP-vollständig ist.

Aufgabe 4

Sei 2 = {0,1}, und sei w € £*. #o(w) gibt an, wie oft die 0 in w vorkommt. Z. B. ist
# (0110100) = 4. Analog zahlt #; (w), die Anzahl der Ziffern 1 in w.

a) Sei

Li= fw] we {0,1} *,#0(w) = Hm).

Beispiele: 010110 e Lı, 1001 e L..

Zeigen Sie, dass L, kontextfrei ist, indem Sie die Arbeitsweise eines deterministischen
Kellerautomaten M genau beschreiben, der L} akzeptiert. (Zu „genau“ gehört auch die
Begründung dafür, warım M Wörter, die nicht in L; sind, verwirft.)

b) Formulieren Sie das Pumping-Lemma für reguläre Sprachen:
„Sei L eine reguläre Sprache über dem Alphabet %. Dann gibt ...“

c) Zeigen Sie mittels Pumping-Lemma für reguläre Sprachen, dass die Sprache L, aus a) nicht
regulär ist.

=.
Herbst 2008 Einzelprüfungsnummer 46113 Seite 3

Thema Nr. 2

Aufgabe 1 (reguläre Ausdrücke und endliche Automaten)

Die Elemente einer regulären Sprache können durch endliche Automaten oder reguläre Ausdrücke
beschrieben werden.

(a) Leiten Sie einen regulären Ausdruck her, der alle Worte über J) = {0,1} beschreibt,
die abwechselnd 0 oder 1 enthalten. Die Sprache sei L.

Beispiel: 0101 € L,1010 € L,0110¢ L
Berücksichtigen Sie alle Möglichkeiten, die Worte aus Z zu bilden. Begründen Sie,
warum der von Ihnen hergeleitete reguläre Ausdruck die Sprache L beschreibt.

(b) Betrachten Sie folgenden deterministischen endlichen Automaten

1
Start sf} —_-5 @-

Welche reguläre Sprache wird von dem Automaten erkannt? Leiten Sie einen regulären Ausdruck ab, der die gleiche Sprache wie der angegebene Automat beschreibt. Bestimmen Sie dazu die regulären Ausdrücke An, wobei An die Menge
aller Worte w beschreibt, die der Beschriftung der Kanten auf einem Pfad zwischen
Zustand q; und q,; des Automaten entsprechen, wobei für keinen der Zwischenknoten q auf dem Pfad ! > k gelten darf. Vereinfachen Sie in den Zwischenschritten
die erhaltenen regulären Ausdrücke so weit wie möglich. Welcher der Ausdrücke
RY beschreibt das Verhalten des gesamten Automaten? Begründen Sie, warum der

von Ihnen hergeleitete reguläre Ausdruck die gleiche Sprache wie der angegebene
Automat beschreibt.

(c) Geben Sie die Aussage des Pumping-Lemmas für reguläre Sprachen wieder.

Beweisen Sie mit Hilfe des Pumping-Lemmas, dass die Sprache L = {0"";n = 1}
nicht regulär ist.

Fortsetzung nächste Seite!
Herbst 2008 Einzelprüfungsnummer 46113

Aufgabe 2 (Grammatiken)

(a)

(c)

(d)

Ein Palindrom ist eine Zeichenkette, die von vorn und von hinten gelesen gleich
bleibt. Beispiele sind otto oder madamimadam (” Madam, I’m Adam”).

Wir betrachten Palindrome über dem Alphabet {0,1}. Geben Sie eine kontextfreie
Grammatik G mit Terminalsymbolen, Nichtterminalsymbolen und Produktionen
an, die alle Palindrome über {0,1} erzeugt. Begründen Sie, warum die von Ihnen
angegebene Grammatik nur Palindrome erzeugt. Geben Sie die Ableitung des Palindroms 11011 mit Ihrer Grammatik an.

Betrachten Sie die Grammatik G = ({E}, {0,1,...,9}, P,E)mit P={E> E+E|
E-E|E+E|E/E|0|1]2|3|4|5|6|7|8| 9} zur Beschreibung arithmetischer Ausdrücke mit den Operatoren {+,—,x,/} über den Ziffern {0,...,9}.
Beweisen Sie, dass diese Grammatik mehrdeutig ist.

Geben Sie eine eindeutige kontextfreie Grammatik zur Beschreibung arithmetischer
Ausdrücke mit den Operatoren {+,—,x*, /} über den Ziffern {0,...,9} an, vgl. Aufgabenteil (b). Beschreiben Sie die Arbeitsweise der Produktionen. Begründen Sie,
warum die von Ihnen angegebene Grammatik eindeutig ist.

Die Sprache L = {a"b"c";n > 1} kann nicht durch eine kontextfreie Grammatik
beschrieben werden. Geben Sie eine kontextsensitive Grammatik zur Beschreibung
von L an, Beschreiben Sie die Arbeitsweise Ihrer Grammatik. Leiten Sie das Wort
aaabbbece € L mit Hilfe Ihrer Grammatik ab.

Aufgabe 3 (kontextfreie Sprachen und Kellerautomaten)

(a)

(b)

Betrachten Sie die kontextfreie Sprache L = {a"1b";n > 1} über dem Alphabet
{a, b,1}. Geben Sie eine kontextfreie Grammatik G mit Terminalsymbolen, Nichtterminalsymbolen und Produktionen an, die L erzeugt.

Konstruieren Sie einen deterministischen Kellerautomaten X = (Q, 3, T, 6, 90, 20, f),
der L erkennt, d.h. Z = L(K). Geben Sie eine genaue Definition aller Elemente des
Kellerautomaten mit einer mathematisch exakten Definition der Übergangsrelation
ö. Erläutern Sie die Arbeitsweise des Kellerautomaten und begründen Sie, warum
K alle Worte aus L erkennt.

Erläutern Sie den Unterschied zwischen nichtdeterministischen und deterministischen Kellerautomaten durch Angabe der exakten Definitionen. Welche Unterschiede in den Verarbeitungsschritten gibt es?

Kann die Sprache L’ = {a"b";n > 1} durch einen deterministischen Kellerautomaten erkannt werden? Begründen Sie Ihre Antwort.

Seite 4