Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl:
Frühjahr
Kennwort: 46 1 13
2000
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: 3

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

Thema Nr. 1

Sämtliche Teilaufgaben sind zu bearbeiten!

Teilaufgabe 1:

Gegeben sei die Grammatik T mit der Menge {a,b,c} von Terminalzeichen, der Menge
{8,A,B,C} von Nicht-Terminalzeichen, dem Startsymbol S und den Produktionsregeln
s- e|aA]b8|cb
A e|ac|bB|cB|cch
B- e|bB
<= elac|bB|cb

(e bezeichne das leere Wort.) 2(T) sei die von I erzeugte Sprache.
a) Beweisen Sie:

ai) aaabbe ¥(T). .

a2) c kommt in jedem Wort von Z(T) höchstens zweimal vor.

a3) Ist we ¥(T) ein Wort, das genau ein c enthält, so enthält w genau ein a oder
genau ein b.

b) Geben Sie einen nicht-deterministischen endlichen Automaten an, der genau die
i Elemente von £(T) äkzeptiert! :

Teilaufgabe 2:
Sei L = {a"bc?”|n € Nj} eine Sprache über dem Alphabet {a,b,c}. Beweisen Sie:
a) L ist nicht regular.

b) . L ist kontext-frei.

Teilaufgabe 3:
Die Funktionen f:N,xN, > N, und g:N,> IN, seien definiert durch:
n-m, falls n2m I, falls 7n € Ng
Anm) = Ir sonst, und an) = ke sonst.

Beweisen Sie:
a) fist primitiv-rekursiv.
b) g ist partiell-rekursiv.

Hinweis: Sie dürfen ohne Beweis voraussetzen, dass die arithmetischen Grundfunktionen
Addition, Subtraktion und Multiplikation primitiv-rekursiv sind!

Frühjahr 2000 Einzelprüfungsnummer: 46113 Seite: 3

Thema Nr. 2

Sämtliche Teilaufgaben sind zu bearbeiten!

Teilaufgabe 1:
a) Gegeben ist eine formale Grammatik G = (S, Z, P, so). Welche Bedingungen müssen die
Produktionen P erfüllen, damit die Grammatik
i) rechtslinear, ii) kontextfrei, iii) kontextsensitiv ist?
Die von G erzeugte Sprache wird mit L(G) bezeichnet. L{G) heißt "vom Typ 3", wenn G

rechtslinear ist, "vom Typ 2", wenn G kontextfrei ist und "vom Typ 1', wenn G kontextsensitiv
ist.

b) Charakterisieren Sie Sprachen vom Typ 3 und vom Typ 2 mit Hilfe von Automatentypen!

c) Gegeben sei die Grammatik G=({A, B}, {0,1}, P, A) mit
P={A-0B,B-01BB-10B8,B—-1}.

i) Geben Sie einen regulären Ausdruck mit Sprache L(G) an!

ii) Konstruieren Sie einen nichtdeterministischen endlichen Automaten, der die Sprache L(G)
akzeptiert!

iii) Konstruieren Sie einen minimalen deterministischen endlichen Automaten, der die Sprache
L(G) akzeptiert!

d) Geben Sie eine Typ 2-Sprache £2 an, die nicht vom Typ 3 ist, zusammen mit einer kontextfreien
Grammatik, die L2 erzeugt!

e) Geben Sie eine Typ 1-Sprache £1 an, die nicht vom Typ 2 ist, zusammen mit einer kontextfreien
Grammatik, die L1 erzeugt!

Teilaufgabe 2:

Gegeben sei die folgende Funktionsdefinition:

function f (n: Nat) : Nat;
ifn=0O then Oelse n+f(n-1) end;

a) Wie lautet das zur obigen Definition gehörige Funktional ©: [NL = N+} = [N+ > N+]?
Zeigen Sie, dass die Funktion

g:Nt—3N mit g(n) =n*(n+1)/2 fallsn#t, gb =,

ein Fixpunkt von © ist! (Hierbei bezeichnet N+ die Menge der natürlichen Zahlen erweitert um
das Element 1.)

b) Beweisen Sie durch Induktion, dass für alle natürlichen Zahlen n gilt: f(n) = n*(n+1)/2.