Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer
Kennzahl:
Frühjahr
Kennwort: 461 13
2003
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: 3

Bitte wenden!

Frühjahr 2003 Einzelprüfungsnummer: 46113 Seite: 2

Thema Nr. 1

1. (Automatentheorie)
a) Geben Sie einen deterministischen endlichen Automaten an, der genau diejenigen Wörter

über {0,1,2} akzeptiert, in denen weder 01 noch 10 vorkommt (d. h., die nicht die Form

u0lv oder ul0v besitzen).
b) Geben Sie einen regulären Ausdruck an, der die Menge dieser Wörter beschreibt!

2. (Formale Sprachen) :
a) Geben Sie eine kontextfreie Grammatik an, die die Sprache {a"b"c"*™: n, m 2 1}
erzeugt!
b) Zeigen Sie mit Hilfe des Pumping-Lemmas, dass diese Sprache nicht regulär ist!

3. (Berechenbarkeit)
Es sei @ dasjenige Wort, das man aus © e {0, 1}* durch das Vertauschen der Symbole 0 und I

erhält, also z. B. 011011000100 = 100100111011.

Man gebe eine 1-Band-Turingmaschine an, die die Funktion f :{0,1}*— {0,1}* mit
- falls der rechteste Buchstabe von @ eine 1 ist

S(@) ae

@ sonst

berechnet. Die Arbeit der Turingmaschine beginnt und endet auf dem linkesten Buchstaben des Eingabe- bzw. Ergebniswortes. Kommentieren Sie die Befehle Ihrer Turingmaschine!

4. (Komplexität)
Geben Sie einen nichtdeterministivchen Algorithmus an, der das Rucksackproblem
annunbe04): TQ 5045 Ay, D,--05Dq 30d E NA (1 c{L...,.mpa ya, < cab = a}
iel iel

in Polynomialzeit löst. Geben Sie eine Laufzeitabschätzung für Ihren Algorithmus an!

Alle Antworten sind zu begründen.
Frühjahr 2003 Einzelprüfungsnummer: 46113 Seite: 3

Thema Nr. 2

1. Durch folgende Grammatik (Großbuchstaben sind Variablen/Nichtterminalsymbole) wird eine
„Programmiersprache“ WHILE definiert:

« SW |whileBdoSend|($;S)
°. W>V=V+1|V=V-1

. V>ıK

K>0|1Z

Z>0Z|1Z\e

B>Vz0

a) Geben Sie einen regulären Ausdruck für die Sprache LK = {w « {0,1} *| w ist aus K ableitbar} an!

b) Geben Sie einen endlichen erkennenden Automaten für LK = {w e{0,1}*|wistausK ableitbar}
an! ,

c) Ist die Sprache WHILE regular, kontextfrei, kontextsensitiv? (Begründung!)

d) Geben Sie eine Beschreibung (Semantik) an, wie Programme aus WHILE auf einer geeigneten
Maschine (beschreiben Sie auch diese!) ausgeführt werden!

e) Geben Sie ein Programm in WHILE an, das die Funktion <x — 2* > berechnet!

2. Geben Sie eine formale Definition für eine zweidimensionale Turingmaschine, die anstelle eines
(eindimensionalen) Turingbandes ein (zweidimensionales, wie auf kariertem Papier in Einheitsquadrate eingeteiltes) unendliches „Turing-Speicherblatt“ besitzt!

3. Sei R ein regulärer Ausdruck und & das leere Wort. Beweisen Sie:
- Ist & inder durch R beschriebenen regulären Sprache L{R), so gilt R'=R
[Hinweis: R* = RR*].

4. Gegeben sei die Sprache L= (Barbara, Bar, Barbar}.

a) Geben Sie eine Grammatik G an, die L erzeugt!
b) Geben Sie einen vollständigen erkennenden endlichen Automaten an, der L akzeptiert!