Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl:
Frühjahr
Kennwort: _______ 46113
2009

Arbeitsplatz-Nr.:

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: 5

Bitte wenden!
Frühjahr 2009 Einzelprüfungsnummer: 46113 Seite: 2

Thema Nr. 1
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Aufgabe 1:
Zur Beschreibung regulärer Sprachen können deterministische endliche Automaten, nichtdeterministische endliche Automaten und reguläre Grammatiken eingesetzt werden.

a)

b)

e)

Betrachten Sie folgenden nichtdeterministischen endlichen Automaten:

0,1
DI
sar—( )——() —_, Ö
qo a &

Erklären Sie die Funktionsweise dieses Automaten und die Rolle der verwendeten Zustände.
Welche Sprache wird von dem Automaten erkannt?

Skizzieren Sie den Teilmengenkonstruktions-Mechanismus zur Berechnung eines äquivalenten
deterministischen endlichen Automaten zu einem gegebenen nichtdeterministischen endlichen
Automaten.

Erläutern Sie die Bedeutung der entstehenden Zustände des deterministischen endlichen Automaten.

Wandeln Sie den im Aufgabenteil a) angegebenen nichtdeterministischen endlichen Automaten
mit Hilfe der Teilmengenkonstruktion in einen deterministischen endlichen Automaten um.
Geben Sie die Zwischenschritte des Verfahrens an und erläutern Sie die Berechnung der entstehenden Zustände.

Erläutern Sie den Mechanismus zur Konstruktion einer äquivalenten regulären Grammatik zu
einem gegebenen deterministischen endlichen Automaten.
Erläutern Sie dabei insbesondere die Bedeutung der erzeugten Produktionen.

Konstruieren Sie zu dem in Aufgabenteil c) konstruierten deterministischen endlichen Automaten eine äquivalente reguläre Grammatik.

Geben Sie dabei insbesondere das Startsymbol, die Menge der verwendeten Nichtterminale
sowie die Menge der erzeugten Produktionen an.

Erläutern Sie die Produktionen und deren Bedeutung.

Betrachten Sie folgende Sprache

L = {x € {0,1}*; x stellt eine durch 4,8 oder 16 teilbare Zahl im Dualsystem dar}

Ist diese Sprache regulär? Begründen Sie Ihre Antwort.

Fortsetzung nächste Seite!
Frühjahr 2009 Einzelprüfungsnummer: 46113 Seite: 3

Aufgabe 2:
Das Pumping-Lemma kann dazu verwendet werden, die Zugehörigkeit von Sprachen zu bestimmten Sprachklassen zu überprüfen.

a)
b)

9)

qd)

f)

Formulieren Sie die Aussage des Pumping-Lemmas für kontextfreie Sprachen.

Verwenden Sie das Pumping-Lemma für kontextfreie Sprachen um zu beweisen, dass die Sprache L = {0"1"2";n > 1} nicht kontextfrei ist.
Erläutern Sie Ihre Vorgehensweise.

Betrachten Sie die beiden Sprachen:

Ly = {rn >152>1}
Lg = {0'1"2";n > 1; > 1}

Beweisen Sie, dass beide Sprachen kontextfrei sind.

Geben Sie jeweils zwei kontextfreie Grammatiken G, und Gy an, die L,, bzw. La erzeugen.
Betrachten Sie die Sprache L’ = L, M Le, die den Schnitt von L, und La beschreibt. Welche
Worte enthalt L’?

Beweisen oder widerlegen Sie die Aussage “Der Schnitt zweier kontextfreier Sprachen ist ebenfalls kontextfrei.“

Konstruieren Sie einen nichtdeterministischen Kellerautomaten, der die Sprache Ly =
{0'1"2";n > 1;4 > 1} aus Aufgabenteil (c) erkennt.

Geben Sie eine genaue Definition aller Elemente des Kellerautomaten mit einer mathematisch
exakten Definition der Übergangsrelation 6. Erläutern Sie die Arbeitsweise des von Ihnen konstruierten Kellerautomaten und begründen Sie, warum der Kellerautomat alle Worte aus La
akzeptiert.

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, aus Aufgabenteil (d) durch einen deterministischen Kellerautomaten
erkannt werden? Begründen Sie Ihre Antwort.
Frühjahr 2009 Einzelprüfungsnummer: 46113 Seite: 4

Thema Nr. 2
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Aufgabe 1:
Für natürliche Zahlen a, b mit 5 > 0 bezeichne div(a,b) den Quotienten und mod(a, b) den Rest
der ganzzahligen Division von a durch b, d.h. es gilt

a=b-div(a,b)-+mod(a,b) mit O<mod(a,b) < b,

und die Divisionseigenschaft der ganzen Zahlen besagt, dass div(a,b) und mod(a,b) durch diese
Beziehung eindeutig bestimmt sind. Für b = 0 sind div(a,b) und mod(a, b) nicht definiert. Mit
ggT(a,b) wird der größte gemeinsame Teiler von a und b bezeichnet, wobei ggT(a,0) = a ist
(vereinbarungsgemäß auch für den Fall a = 0).

a) Zeigen Sie, dass mod eine primitiv-rekursive Funktion ist.
b) Zeigen Sie, dass div eine primitiv-rekursive Funktion ist.

c) Geben Sie ein LooP-Programm zur Berechnung von ggT an.

Aufgabe 2:
Betrachten Sie über dem Alphabet © = {a,b} die Sprache

L= {w € 2* ;|w|. ist ungerade und |w|, ist durch 3 teilbar},

wobei |w|. die Anzahl der a’s in w und |w|, die Anzahl der b’s in w ist. Konstruieren Sie den
minimalen deterministischen endlichen Automaten, der die Sprache L akzeptiert.

Aufgabe 3:
Betrachten Sie über dem Alphabet 2 = {a,b} die Sprache

L={a’b ;r<s<2r}.

a) Beweisen Sie, dass die Sprache L nicht regulär ist.

b) Konstruieren Sie einen Kellerautomaten, der die Sprache L akzeptiert.

Fortsetzung nächste Seite!
Frühjahr 2009 Einzelprüfungsnummer: 46113 Seite: 5

Aufgabe 4:
Welche folgenden Behauptungen über Sprachen A, B C %* sind korrekt, und welche sind falsch?

Begründen Sie Ihre Antwort. (A \\ B bezeichnet die Mengendifferenz.)

a) Sind A und B regulär, so ist auch A \ B regular.

b) Sind A und B kontextfrei, so ist auch A \ B kontextfrei.

c) Sind A und B entscheidbar, so ist auch A \ B entscheidbar.

d) Sind A und B partiell-entscheidbar, so ist auch A \ B partiell-entscheidbar.

e) Sind A und B polynomiell-entscheidbar (d.h. in der Komplexitätsklasse P), so ist auch A \ B
polynomiell-entscheidbar.

Aufgabe 5:
Sei © ein endliches Alphabet.

a) Beschreiben Sie einen Algorithmus, der für beliebige endliche Automaten A =
(Qa, =, 654,94, Fa) und B = (Q,%,6p,95, Fg) entscheidet, ob sie die gleiche Sprache akzeptieren, d.h. ob L(A) = L(B).

b) Zeigen Sie, dass es keinen Algorithmus gibt, der für beliebige deterministische Turingmaschinen
A = (Qa,¥,T 4, 54,94, Fa) und B = (Qz,5,T 2, 58,98, Fp) entscheidet, ob sie die gleiche
Sprache akzeptieren, d.h. ob L(A) = L(B).