Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl:

Herbst
Kennwort: 46 1 13
2001

Arbeitsplatz-Nr.:

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

- Prüfungsaufgaben -
Fach: Informatik (nicht vertieft studiert)
Einzelprüfung: Theoretische Informatik

Anzahl der gestellten Themen (Aufgaben): 2

Anzahl der Druckseiten dieser Vorlage: 2

Thema Nr. 1

1. (Automatentheorie) Für n > 0 sei LZ, =cer {a, b}*a{a, b}"a{a, b}* die Menge aller Wörter aus
{a, b}*, in denen der Buchstabe a an zwei Stellen mit genau n dazwischenliegenden Buchstaben
vorkommt. Geben Sie einen nichtdeterministischen endlichen Automaten mit n + 3 Zuständen an,
der L, akzeptiert (erkennt)!

2. (Formale Sprachen) Geben Sie eine kontextfreie Grammatik an, die die Sprache
L =ser {a"b” : 0 <n < m} erzeugt! Zeigen Sie weiter, dass diese Sprache nicht regular ist!

3. (Berechenbarkeit) Zeigen Sie, dass die Sprache {(13n° - 17m)? : n,m € N} rekursiv aufzählbar ist!
4. (Komplexität) Es sei exp : N”— N mit exp(x,y) =aerx” die Exponentialfunktion.
a) Ist exp in polynomieller Zeit berechenbar?

b) Zeigen Sie durch Angabe eines geeigneten Algorithmus, dass die Menge {(x,y,2) :x’=z} in
polynomieller Zeit entscheidbar ist!

Alle Antworten sind zu begründen.
Herbst 2001 Einzelprüfungsnummer: 46113 Seite: 2

Thema Nr. 2

Aufgabe 1 (Automatentheorie)
Gegeben seien das Alphabet /= (4,B,C) und die regulären Mengen Rı und R» über dem Alphabet 7:
Ri = {{AB}*{C} {C}*}* und Ro = {{AB}*{C}}*.
Beweisen Sie, dass Rı = R; ist!
Hinweis: Für den Beweis empfiehlt es sich, endliche Automaten A; und A» zu konstruieren, deren akzeptierte
Wortmengen L(A,) = R, und L(A2) = R, sind.
Aufgabe 2 (Formale Sprachen)

Gegeben seien das terminale Vokabular V7 = (a,b,c) und die drei Wortmengen Zı, L>, L3, über dem
Vokabular Yr:

Lean la en.

1. Diese drei Wortmengen sind kontextabhängige Sprachen. Eine von ihnen ist darüber hinaus kontextfrei. Stellen Sie fest, welche das ist, und konstruieren Sie dafür eine CHOMSKY-2-Grammatik!

2. Beweisen Sie für eine der beiden anderen Sprachen, die Sie selbst auswählen können, dass sie

nicht kontextfrei ist, und konstruieren Sie dafür eine CHOMSKY-1-Grammatik!

Aufgabe 3 (Berechenbarkeit)
Gegeben sei die Funktion c: Mj > N mit c(x) = entier e vx) 1.

1. Beweisen Sie, dass die Funktion c(x) primitiv rekursiv ist!

Hinweis: Für den Beweis können Sie anstelle des Modells der primitiv rekursiven Funktionen ein dazu äquivalentes Programmiermodell verwenden.

2. Geben Sie eine vollständige z-rekursive Herleitung der Funktion c(x) an, in der eine Minimalisierung verwendet wird!

entier(a) ist die größte ganze Zahl, die kleiner oder gleich a ist.