Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl:

Herbst
Kennwort: 461 13 .

2005

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

Bitte wenden!
Herbst 2005 Einzelprüfungsnummer: 46113

>
Seite: 2 ~

Thema Nr. 1

Sämtliche Teilaufgaben sind zu bearbeiten!

Vorbemerkung: Bei der Lösung von Teilaufgaben können (wenn möglich) Lösungen der vorherigen Teilaufgaben vorausgesetzt werden, auch wenn diese nicht gelöst wurden.

Aufgabe 1

Gegeben ist der folgende nichtdeterministische endliche Automat A mit Leerübergängen. (Ein
Leerübergang hat die Markierung "e" und besagt, dass der Automat (spontan) einen Zustandswechsel durchführen kann ohne ein Eingabezeichen zu lesen.)

Es bezeichne L(A) die von A akzeptierte Sprache.

a) Konstruieren Sie einen äquivalenten Automaten ohne Leerübergänge.
b) Konstruieren Sie einen äquivalenten, minimalen deterministischen Automaten.

c) Beweisen Sie unter Verwendung des in Teil b) konstruierten minimalen Automaten, dass
für jedes w € L(A) gilt: Die Anzahl der in w vorkommenden Zeichen b ist gerade.

d) Geben Sie einen regulären Ausdruck an, der die Sprache L(A) beschreibt.

e) Geben Sie eine rechtslineare Grammatik an, die die Sprache L(A) erzeugt.
Herbst 2005 Einzelprüfungsnummer: 46113 Seite: 3

Aufgabe 2

Für eine primitiv rekursive Funktion f : N + N sei die (von f abhängige) Menge My C N
folgendermaßen definiert (wobei N die Menge der natürlichen Zahlen einschließlich der 0 bezeichnet):

M; = {zeN|32<z2,fß)=2}

a) Geben Sie primitiv rekursive Funktionen fl und f2an mit Mp, = N und Ma = {0}.

b) Zeigen Sie, dass es keine primitiv rekursive Funktion f gibt mit My = 0.

Es soll nun bewiesen werden, dass M; primitiv rekursiv ist, d.h. dass die charakteristische Funktion xu, : N > N (mit xu, (2) = 1 falls x € My, xm;(z) = 0 sonst) primitiv rekursiv ist. Zum
Beweis sind die Teilaufgaben c) und d) zu bearbeiten.

c) Die (von f abhängige) Funktion ©; : N 2 — N wird definiert durch

1 falls32 <ymit f(2)=x
Bay) = h sonst

Zeigen Sie, dass ®, primitiv rekursiv ist. Beim Beweis ist das Schema der primitiven
Rekursion mit geeigneten primitiv rekursiven Funktionen g : N-Nwudh:N’-N
zu verwenden. Dabei kann vorausgesetzt werden, dass die Funktionen eq : N 2 _, N und
or : N? + N primitiv rekursiv sind, wobei eq(z, y) = 1 falls x = y, eg(x,y) = 0 sonst
und or(z,y) = 1 falls x # 0 oder y # 0, or(x,y) = 0 sonst.

d) Zeigen Sie unter Verwendung von Teil c), dass M, primitiv rekursiv ist.

Herbst 2005 Einzelprüfungsnummer: 46113 Seite” 4

Thema Nr. 2

Aufgabe 1

Gegeben sind die drei folgenden Sprachen Z,,Z, und L (jeweils über dem Alphabet {a,5,c}).
L, = {a'‘c* |4,k > 0}

L, = {a'd'c* |,k > 0}

lhe [act | i,j,k > 0, = joderj = i}

a) Beweisen Sie, dass Z, nicht regulär ist!
b) Geben Sie kontextfreie Grammatiken G, und G, an, die die Sprachen L, bzw. L, erzeugen!

c) Wie kann man aus den beiden Grammatiken für L, und L, eine Grammatik G konstruieren, die
die Sprache L erzeugt? (Begründung ohne Beweis!)

d) Zeigen Sie, dass die in Teil c) konstruierte Grammatik G mehrdeutig ist!

e) Ist die Sprache L, OL, kontextfrei? (Begründung ohne Beweis!)

Aufgabe 2 =

Geben Sie einen vollständigen deterministischen endlichen Automaten (etwa in Form eines Zustandsdiagramms) an, der genau diejenigen Worte aus {a,b} * akzeptiert, die an drittletzter Position
das Zeichen a stehen haben. Begründen (beweisen) Sie, dass der Automat alle diese und nur diese
Worte akzeptiert!

Hinweis: Konstruieren Sie zuerst einen nichtdeterministischen endlichen Automaten, der die genannte Menge akzeptiert.