Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl:
Frühjahr
Kennwort. — 461 13
2008

Arbeitsplatz-Nr.:

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

— Prüfungsaufgaben —

Fach: Informatik (Unterrichtsfach)
Einzelprüfung: Theoretische Informatik, Algorithmen
Anzahl der gestellten Themen (Aufgaben): 2

Anzahl der Druckseiten dieser Vorlage: 5

Bitte wenden!
Frühjahr 2008 Einzelprüfungsnummer: 46113 Seite: 2
Thema Nr. 1

Aufgabe 1:
reguläre Mengen

Sei L die Menge aller Worte über dem Alphabet tab, c}, deren drittes Zeichen (von links) ein a
und deren vorletztes Zeichen ein b ist.

Beschreiben Sie L
a) durch einen regulären Ausdruck,

b) durch einen deterministischen endlichen Automaten A.

Aufgabe 2:
Klassifikation von Sprachen

‘Was ist kleinste Klasse der Chomsky-Hierarchie, in der die Sprache
L = {a"b"c" |0 <n < 100} liegt.
Begründen/beweisen Sie Ihre Antwort!

Sie dürfen hierzu bekannte Eigenschaften von Klassen der Chomsky-Hierarchie verwenden, ohne diese selbst zu beweisen, z. B. Pumping Lemmata für reguläre bzw. kontextfreie Sprachen oder entsprechende Automaten oder Maschinen bzw. Grammatiken.
Bei der Angabe von Automaten oder Maschinen müssen Sie „high-level“ beschreiben, wie
der Automat/die Maschine arbeiten soll.

Aufgabe 3:
Determinismus und Nicht-Determinismus

Gegeben sind

a) endliche Automaten,
b) Kellerautomaten und
c) Turingmaschinen.

Für welche dieser Maschinen gilt, dass die deterministischen und die nicht-deterministischen
Maschinen gleichmächtig sind bzw. dass dies nicht gilt?

Begründen Sie Ihre Antwort für (beliebige) zwei der drei Fälle a) - c)! Im Fall der Gleichmächtigkeit. müssen Sie zur Begründung angeben, wie eine nicht-deterministische Maschine durch eine
äquivalente deterministische simuliert wird. Der Beweis der Äquivalenz ist nicht gefordert.
Andernfalls ist der Nachweis anhand passender und bekannter Gegenbeispiele zu führen.

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

Aufgabe 4:
Konstruktion von Turingmaschinen
a) Konstruieren Sie eine (k-Band-)Turingmaschine M für die Sprache

COPY = {wew|w € {a,b}*}.

b) Welche Zeit-Komplexität hat Ihre Turingmaschine M?
c) Ordnen Sie COPY in die Chomsky-Hierarchie ein.

Aufgabe 5:

kontextfreie Sprachen

Zeigen Sie durch Angabe einer kontextfreien Grammatik G‘, dass die Sprache L der Palindrome
über dem Alphabet {a,b,c}
L = {w € {a,b,c}*|w=w"™ }

kontextfrei ist, wobei w" die Spiegelung von w ist (w wird rückwärts gelesen).

Aufgabe 6:
kontextfreie Sprachen

Zeigen Sie, dass die Sprache
L = {a"b"|n > 0,m > 0,n = m oder n = 2m}

kontextfrei ist.

Es reicht die Angabe einer geeigneten Grammatik oder eines geeigneten Automaten. Was „geeignet“ ist, muss gesagt werden.
Frühjahr 2008 Einzelprüfungsnummer: 46113 Seite: 4

Thema Nr. 2

Aufgabe 1:
Primitiv rekursive Funktionen

Geben Sie für die folgenden Funktionen primitiv rekursive Terme an. In jeder Teilaufgabe können
Sie die Funktionen der vorangegangenen Teilaufgaben als primitiv rekursiv voraussetzen.

a) Die Bedingung if:NxNx N— N:mit

z falls b>0

y sonst

if(b,2, 9) = {
b) Die Vorgingerfunktion pred : N > N mit

z-1falls2>0
0 sonst

pred(z) = {
c) Die absolute Differenz dff:NxN— N mit

diffla,y) = {; ee

y — az sonst
d) Das Gleichheitspradikat eq: N x N > N mit

1 falls = y
eq(z,y) = {i sonst

Aufgabe 2:
Typ-1-Sprachen
Gegeben sei die Sprache L = {a*b?#ck | k € N}.

a) Zeigen Sie, indem Sie eine geeignete Grammatik angeben: L ist kontextsensitiv.

b) Verwenden Sie das Pumping-Lemma für kontextfreie Sprachen (uvwxy-Theorem), um zu zeigen: L ist nicht kontextfrei.

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

Aufgabe 3:
Cocke-Younger-Kasami- Algorithmus

Es sei G = ({A, B,C, D, E, F,G, H, I} ,{d,q,m,p, b} , P, A) die kontextfreie Grammatik mit dem
Startzustand A und den folgenden Regeln P in Chomsky-Normalform.

A FBIFC
BAG
C— DG
D— HE\|HI
&— DI
F—od
Gob
H-q
Iop

a) Zeigen Sie mit Hilfe des Algorithmus von Cocke, Younger und Kasami (CYK), dass
ddgpbb € L(G).

b) Zeigen Sie mit Hilfe CYK-Algorithmus, dass ddqgppb ¢ L(G).

Aufgabe 4:
Kellerautomaten

Es sei L = {abe |ie N}
a) Geben Sie eine kontextfreie Grammatik G' an, so dass L(G) = L.

b) Geben Sie einen nicht-deterministischen Kellerautomaten M = (Q,),T, 6,90, #) an, der die
Sprache L akzeptiert, und erläutern Sie seine Funktionsweise.