Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl:
H
Kennwort: erbst 46113
| 2014 |
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 2014 Einzelprüfungsnummer: 46113 Seite: 2

Thema Nr. 1
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu ‚bearbeiten!

Aufgabe 1:
Wir fixieren das Alphabet 3 = {0,1} und definieren L C &* durch

L = {w | in w kommt das Teilwort 0010 vor}

a) Zeigen Sie, dass L regulär ist.

b) Vervollständigen Sie durch Hinzufügen von Kanten und Angabe der Endzustände folgendes
Diagramm zu einem deterministischen Automaten für L. Bitte das Diagramm auf Ihrem Arbeitspapier noch einmal abschreiben.

0 0 1 0
>? do -> dı =? G2 -> 93 —? 4

c) Zeigen Sie durch Ausführung des Minimierungsalgorithmus, dass dieser Automat minimal ist.

d) Geben Sie die Äquivalenzklassen der Myhill-Nerode-Äquivalenz von L durch Repräsentanten
an. (Diese Aquivalenz ist definiert durch tr ~, y <=> Vu: tue Le ye L.)

Geben Sie zu zwei Klassen Ihrer Wahl neben dem gewählten Repräsentanten noch ein weiteres
Element an.

Geben Sie für die Klasse, in der sich das leere Wort befindet, einen regulären Ausdruck an.
Hilfe: Diese Klasse ist identisch mit {w | 10001w e L}.

Aufgabe 2:

Ordnen Sie die folgenden formalen Sprachen bestmöglich in die Chomsky-Hierarchie ein und geben
Sie eine ausreichende Begründung an:

a) ı =[a"rba”|n>1}
b) Ly = {a™b"c" |n>1}

c) Lg sei die Menge aller syntaktisch korrekten Java-Programme, die ohne Eingabe terminieren.

Aufgabe 3:

Bekanntlich sind beim SUBSET-SUM Problem natürliche Zahlen aı,...,q, und eine Zielzahl b
gegeben und es ist gefragt, ob eine Teilmenge J C {l,...,n} existiert, sodass )_,., ai = b. Dieses
Problem ist bekanntermaßen NP-vollständig.

a) Zeigen Sie, dass die Variante GSUBSET, bei der die Zahlen a; und b allesamt gerade sein
müssen, ebenfalls NP-vollständig ist.

b) In welche Komplexitätsklasse fällt die Variante ZSUBSET, bei der die a; paarweise verschieden
und Zweierpotenzen sind? Hilfe: Betrachten Sie die Binärdarstellung von b.
Herbst 2014 Einzelprüfungsnummer: 46113 Seite: 3

Thema Nr. 2
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Aufgabe 1:
Sei D = {a,b}, sei Ng = {0,1,2,...}.
a) Sei
L, = {a”b"InmeNo,n>m>0}.
Beispiele: aab € Lı, aaaabb € L,, a € Ly.

i) Zeigen Sie, dass L, kontextfrei ist, indem Sie eine kontextfreie Grammatik G angeben mit
L(G) = Ly, und

ii) begründen Sie, warum Ihre Grammatik genau die Sprache L, erzeugt.

b) Formulieren Sie das Pumping-Lemma für reguläre Sprachen:
„Sei L eine reguläre Sprache über dem Alphabet 3. Dann gibt es...“

c) Zeigen Sie mit Hilfe des Pumping-Lemmas für reguläre Sprachen, dass die Sprache L, nicht
regulär ist.

Aufgabe 2:

a) Definieren Sie die zum Halteproblem für Turing-Maschinen bei fester Eingabe m e N, =
{0,1,2,...} gehörende Menge H,„.-
Es geht hier also um die Turing-Maschinen, die mit fest vorgegebener Eingabe m gestartet
werden.

b) Gegeben sei das folgende Problem E:
Entscheide, ob es für die deterministische Turing-Maschine M,„ mit der Gödelnummer n

mindestens eine Eingabe w € N, gibt, so dass w eine Primzahl ist und die Maschine M,,
gestartet mit w hält.

Zeigen Sie, dass E nicht entscheidbar ist. Benutzen Sie, dass H,, aus (a) für jedes m € No
nicht entscheidbar ist.

c) Zeigen Sie, dass das Problem E aus (b) partiell-entscheidbar (= rekursiv aufzählbar) ist.

Aufgabe 3:

a) Konstruieren Sie aus dem NEA A mit der Potenzmengenkonstruktion einen (deterministischen) EA, der dieselbe Sprache akzeptiert.

A:

b) Welche Sprache wird von dem regulären Ausdruck (a + b)*a(a + b) beschrieben?

Fortsetzung nächste Seite!
Herbst 2014 Einzelprüfungsnummer: 46113 Seite: 4

Aufgabe 4:

a) Gegeben sei die folgende kontextfreie Grammatik G = (V,D,P,S) mit V = {8,A,B,C,D},
% = {a,b,c} und den Produktionen:

5 — AlaB|aCc B- 5]|Ba D — b|bDD

A — B\|C|cAd C —+ Dic

Konstruieren Sie eine äquivalente kontextfreie Grammatik G’ ohne Kettenregeln, so dass
L(G’) = L(G) gilt.

Hinweis: Eine Produktion heißt Kettenregel, wenn sie von der Form A — B für Variablen A
und B ist.

b) Sei G = (V, 2, P, S) folgende kontextfreie Grammatik in Chomsky-Normalform:
S —+ AB|BC B- CC|b
A — BAla C + ABla

Sei w = ababa. Folgende Tabelle entsteht durch Anwendung des CYK-Algorithmus. Geben Sie

die drei fehlenden Eintrage V(1, 4), V(2,5) und V(1, 5) an. Wie entnehmen Sie dieser Tabelle,
dass w € L(G) ist?

a b a b a
{A,C} {B} {A,C} {B} {A,C}
{5,0} {S.A} {5,0} {S.A}

{B} {5,0} {3}
1,9 v2,5)
W1,5)