Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl:

Frühjahr
Kennwort: A6 1 1 3
2011

Arbeitsplatz-Nr.:

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

— Prüfungsaufgaben —

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

Anzahl der Druckseiten dieser Vorlage: 5

Bitte wenden!


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

I'hema Nr. 1
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Aufgabe 1:
Formale Sprachen

a) Betrachten Sie den folgenden deterministischen endlichen Automaten:
1

oe
Start ens

1
0 0 0 0

a
OMS
Dieser Automat erkennt die Sprache
Lı = {w | w € {0,1}*, w hat gerade Anzahl von Oen und len }
Modifizieren Sie den Automaten so, dass er die Sprache

Lo = {w |w e {0,1}*, w hat ungerade Anzahl von Oen und len }

erkennt. Begründen Sie die von Ihnen vorgeschlagene Modifikation.
b) Erweitern und modifizieren Sie den gegebenen Automaten aus Aufgabenteil (a) so, dass er die
Sprache
Ls = {w | w € {0,1,2}*, w hat ungerade Anzahl von Oen, len und 2en }

erkennt. Erläutern Sie die Arbeitsweise des von Ihnen konstruierten Automaten.

c) Beschreiben Sie, was man unter der Äquivalenz von Zuständen in deterministischen endlichen
Automaten versteht. Geben Sie eine exakte Definition mit Hilfe der Übergangsfunktion an.
Beschreiben Sie die Arbeitsweise des Algorithmus zur Bestimmung der äquivalenten Zustände
eines deterministischen endlichen Automaten.

d) Wenden Sie den Algorithmus auf den folgenden deterministischen endlichen Automaten
M = ({A,B,C,D,E,F,G,H},{0,1},6,A,{D}) an, wobei die Übergangsfunktion 6 durch
folgende Tabelle gegeben ist:

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

e)
f)

g)

au you
QyaQoosesepye
SQ ae BAQAwBr

Bauen Sie dazu die vollständige Tabelle des Algorithmus mit Zustandspaaren schrittweise auf
und erläutern Sie die durchgeführten Schritte.

Fassen Sie anschließend die äquivalenten Zustände zusammen und konstruieren Sie einen äquivalenten deterministischen endlichen Automaten mit einer minimalen Anzahl von Zuständen.
Geben Sie das Übergangsdiagramm des äquivalenten Automaten an.

Formulieren Sie die Aussage des Pumping-Lemmas für reguläre Sprachen. Wie kann das
Pumping-Lemma dazu verwendet werden, zu zeigen, dass eine Sprache nicht regulär ist?

Beweisen Sie mit Hilfe des Pumping-Lemmas aus Aufgabenteil (e), dass die Sprache
Lg = {0"10"1 |n>1}

nicht regulär ist. Erklären Sie Ihre Argumentation.

Betrachten Sie die folgende Sprache
Ls = {ab"c™d™ |n >1,m> 1} U {a™b™e"d” |n > 1,m> 1}

Geben Sie eine kontextfreie Grammatik an, die diese Sprache beschreibt.

Aufgabe 2:
Turingmaschinen

a)

Das Grundmodell einer Turingmaschine kann zur Vereinfachung der Programmierung erweitert
werden, indem das Band der Turingmaschine in mehrere Spuren unterteilt wird. Erläutern Sie
diese Erweiterung. Wie sieht in diesem Fall die Übergangsfunktion aus? Erklären Sie, warum
eine Turingmaschine mit mehreren Spuren nicht mächtiger ist als eine Turingmaschine mit
einer Spur.

Konstruieren Sie eine Turingmaschine mit zwei Spuren zum Erkennen der Sprache
L= {wew | w € {0,1}*}

mit c als Markierungszeichen. Verwenden Sie dabei die 2. Spur als Markierungsspur zur Markierung von bereits gelesenen Symbolen. Geben Sie die Übergangsfunktion im Detail an.
Erläutern Sie die Funktionsweise der von Ihnen konstruierten Turingmaschine.
Frühjahr 2011 Einzelprüfungsnummer: 46113 Seite: 4

Thema Nr. 2
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Aufgabe 1:
Profile als formale Sprachen

Ein Profil ist eine endliche Folge p = pıpa... pn von ganzen Zahlen p; mit n > 1, pı = 9, = 0 und
Ipirı - p| <1fürl<i<n. Die Höhe eines Profils p ist h(p) = maxı<icn |Pil.

Als Beispiel: (0,+1,0,—-1,—1,—-2,—1,0) ist ein Profil der Höhe 2. Die Folge
(0,+1,—1,—1,—2, —1,0) ist kein Profil, da —1 auf +1 folgt. Die Folgen (+1,0, —1,—1,—2, —1,0)
bzw. (0,+1,0,—1,—1,—2,—1) sind keine Profile, da sie nicht mit 0 beginnen bzw. enden.

Die Menge P, der Profile mit Höhe < k kann man als eine Sprache über dem Alphabet
Uy = {0,+1,+2,...,+k} auffassen.

a) Zeigen Sie, dass die Sprache P, regulär ist, indem Sie einen endlichen Automaten angeben,
der diese Sprache akzeptiert.

b) Zeigen Sie, dass die Sprache P=%5\ P regulär ist, indem Sie einen regulären Ausdruck für
P, angeben.

c) Zeigen Sie, dass alle Sprachen P, (k > 0) regulär sind, indem Sie entweder die Konstruktion geeigneter endlicher Automaten für deren Akzeptanz oder die Konstruktion geeigneter
Grammatiken für deren Generierung beschreiben.

Unter der Differenz eines Profils p = pyp2... Py vesteht man das Wort 6(p) = wiwe...Wn—-1 © UF
mit w; = piri — pi (1 <2 <n). Die Differenz des Profils 0 ist das leere Wort.

d) Zeigen Sie, dass die Sprachen DP, = {6(p); p € P,} © Li der Differenzen von Profilen regular
sind.

e) Zeigen Sie, dass für die Sprache aller Differenzen von Profilen DP := J...) DP, © UF gilt:

Ywıwa...Un EI: wıw...Wm © DPS wy + Wo tees + Wn = 0

und diese Sprache nicht regular ist.

f) Zeigen Sie, dass DP eine kontextfreie Sprache ist, indem Sie entweder einen Kellerautomaten
konstruieren, der die Sprache DP akzeptiert, oder indem Sie eine geeignete Grammatik für
die Generierung von DP angeben.

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

Aufgabe 2:
Das Nullfunktionsproblem

Das Nullfunktionsproblem stellt die Aufgabe, von beliebigen Programmen P (Turing-Maschinen,
While-Programme, universelle Programmiersprache etc.) zu entscheiden, ob sie bei jeder Eingabe
halten und das Resultat O liefern.

Es sei Po(z), Pı(z), Pz(z),... eine berechenbare Auflistung aller Programme bzw. Maschinen des
betrachteten Formalismus. Diese Programme haben einen Eingabeparameter 2, der mit natürlichen Zahlen belegt werden kann. Die Schreibweisen P,(z) | bzw. P,(z) T sollen bedeuten, dass
das Programm P, bei Input z terminiert bzw. nicht terminiert. Bei (partiellen) Funktionen f(z)
bedeuten die Schreibweisen f(z) | baw. f(z) 7, dass f(z) definiert bzw. nicht definiert ist.

Es geht bei dem Nullfunktionsproblem um die Menge
D={rteN|VzeN: Plz) = 0}.

a) Zeigen Sie unter Berufung auf die These von CHURCH, dass die Funktion

(2,y) = 0 falls P,(x) |
ENT falls Pula) t

(partiell-)berechenbar ist. .

b) Zeigen Sie, dass die Menge D unentscheidbar ist, indem Sie die Funktion g der vorigen
Teilaufgabe für eine Reduktion verwenden.

c) Bei dem A quivalenzproblem für Programme betrachtet man die Menge

A={(z,y)ENxN | Vz EN: P,(z) = P,(z) }.

Zeigen Sie mittels einer geeigneten Reduktion, dass diese Menge unentscheidbar ist.