Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl:

Herbst
Kennwort: __________ 46 1 1
2016 °

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

Bitte wenden!
Herbst 2016 Einzelprüfungsnummer: 46113 Seite: 2

Thema Nr. 1
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Aufgabe 1:
Reguläre Sprachen

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

A:

b) Beschreiben Sie möglichst einfach, welche Sprachen von den folgenden regulären Ausdrücken
beschrieben werden:

1. (a | b)*a
2. (a | b)*a(a | b)*a(a | b)*
3. (a | b)*a(bb)*a(a | b)*

Aufgabe 2:
Kontextfreie Grammatiken

Betrachten Sie die folgende kontextfreie Grammatik G = ({S, A,B,C}, {a,b,c}, 5,P) mit den
Produktionen:

S->AB|C
A-ale

B- BC

Cc

a) Beschreiben Sie in Worten möglichst genau die von G erzeugte Sprache L(G).

b) Geben Sie ohne Begründung an, welche Variablen in der Grammatik

- nützlich,
- erzeugend oder
- erreichbar

sind!

c) Ist die Grammatik in Chomsky-Normalform? Begründen Sie Ihre Antwort.

Fortsetzung nächste Seite!
Herbst 2016 Einzelprüfungsnummer: 46113 Seite: 3

Aufgabe 3:

Klassifizierung von Sprachen

Welche der folgenden Sprachen über dem Alphabet {a,b} sind

a) regulär?
b) kontextfrei, aber nicht regulär?
c) nicht kontextfrei?
1. Li = {we {a}* | die Länge von w ist 2° für eine natürliche Zahl n}
2. Le = {a*b’ | k < OU {a*b’ | k > of
3. Ls = {a*b’ | k < fh U {akb! | k > 2}
Geben Sie zu Ihrer Antwort jeweils einen Beweis an. Ein Beweis durch Angabe eines Automaten

oder eines regulären Ausdruckes ist erlaubt. Wird der Beweis durch die Angabe einer Grammatik
geführt, so ist die Bedeutung der Variablen zu erläutern.

Aufgabe 4:

Probleme und Komplexität

Betrachten Sie die beiden folgenden Probleme:

VERTEXCOVER

Gegeben: Ein ungerichteter Graph G = (V, E) und eine Zahl k € {1,2,3,...}.

Frage: Gibt es eine Menge C C V mit |C| < k, so dass für jede Kante (u,v) aus E mindestens
einer der Knoten u und v in C ist?

VERTEXCOVER3

Gegeben: Ein ungerichteter Graph G = (V, E) und eine Zahl k € {3,4,5,...}.

Frage: Gibt es eine Menge C C V mit |C]| < k, so dass für jede Kante (u,v) aus E mindestens
einer der Knoten u und v in C ist?

Geben Sie eine polynomielle Reduktion von VERTEXCOVER auf VERTEXCOVER3 an und begründen Sie anschließend, dass Ihre Reduktion korrekt ist.

Aufgabe 5:
Kurze Begründungen

Sind folgende Aussagen wahr oder falsch? Begründen Sie jeweils kurz.

a) Für jede reguläre Sprache R gibt es eine kontextfreie Grammatik G mit L(G) = R.

b) Falls L = L, Le mit L, und Lz kontextfrei, dann ist L eine unentscheidbare Sprache.
c) Falls r ein regulärer Ausdruck ist, so definiert r* immer eine unendliche Sprache.

d) Eine entscheidbare Sprache ist niemals leer.

e) Alle Sprachen in NP sind entscheidbar.
Herbst 2016 Einzelprüfungsnummer: 46113 Seite: 4

Thema Nr. 2
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Aufgabe 1:
Sei & = {0,1}, sei No = {0,1,2,...}.
a) Sei
Ly = {0"1"0"1" | n,m E No} .
Beispiele: 001011 € £,, 1100 € £,, 0101 € Ly.

(al) Zeigen Sie, dass L, kontextfrei ist, indem Sie eine kontextfreie Grammatik G angeben mit
L(G) = Ly, und (a2) 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 D. Dann gibt es...“

c) Sei Lz = {0"10* | n,m,k € No,n > 1,m > 1,k > 1}. Zeigen Sie, dass L, die Eigenschaft des
Pumping-Lemmas für reguläre Sprachen (vgl. (b)) besitzt.

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

Aufgabe 2:

Im Nachfolgenden bezeichne M immer eine deterministische Turingmaschine, die als Eingabe eine
natürliche Zahl bekommt, und (M) sei Gödelnummer von M.

a) Zeigen Sie, dass die Menge

Lı = {(M) |es gibt mindestens eine Zahl n, so dass M gestartet
mit n hält}
rekursiv aufzählbar (= partiell-entscheidbar) ist.

Geben Sie dazu einen Algorithmus A an, der als Eingabe eine Gödelnummer (M) bekommt
und damit gestartet genau dann halt, wenn (M) € Ly ist.

b) Sei Co-Ho = {{M) | M gestartet mit 0 hält nicht}. Es ist bekannt, dass Co-Hp nicht rekursiv
aufzählbar (= partiell-entscheidbar) ist.

Zeigen Sie durch Reduktion von Co-Ho, dass die Menge

Ly = {(M) | es gibt genau eine Zahl n, so dass M gestartet mit n
hält}

nicht rekursiv aufzählbar (= partiell-entscheidbar) ist. Zeigen Sie also konkret: Co-Hp < Le.

Fortsetzung nächste Seite!
Herbst 2016 Einzelprüfungsnummer: 46113 Seite: 5

Aufgabe 3:

a) Gegeben sei der folgende nichtdeterministische endliche Automat N:

011

Konstruieren Sie zu N mit der Potenzmengen-Konstruktion einen äquivalenten deterministischen endlichen Automaten A. Zeichnen Sie nur die vom Startzustand aus erreichbaren
Zustände ein, die aber alle. Die Zustandsnamen von A müssen erkennen lassen, wie sie zustande gekommen sind. Führen Sie keine „Vereinfachungen“ durch!

Hinweis: In einem deterministischen endlichen Automaten muss es an jedem Zustand für jedes
Zeichen einen Übergang geben.

b) Geben Sie einen regulären Ausdruck a{N) für die Sprache an, die der nichtdeterministische
endliche Automat N aus (a) akzeptiert.

c) Beweisen oder widerlegen Sie die folgende Behauptung.

Beh.: Es gibt reguläre Sprachen L, so dass es eine Teilmenge U von L gibt, die nicht regulär
ist.

Aufgabe 4:

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

S + A|Bla A + ClaBb B+ Aalb C — S{bA

Konstruieren Sie eine kontextfreie Grammatik G’, in der es keine Ketten-Produktionen mehr
gibt, mit L(G’) = L(G).

Hinweis: Eine Kettenproduktion ist eine Produktion der Form A - B für A, BEV.

b) Sei G = (V,D,P,S) eine kontextfreie Grammatik in Chomsky-Normalform, und sei
w= Wı...w, ein Wort aus n Zeichen aus dem Alphabet %. Der Algorithmus von Cocke/Younger/Kasami (CYK-Algorithmus) berechnet für alle 7,7 € {1,...,n}, i < j, die Variablenmenge V(i,7) = {A € V | A w;...w;}-

Fortsetzung nächste Seite!
Herbst 2016

Einzelprüfungsnummer: 46113

Sei G = (V, 3, P, S) die kontextfreie Grammatik in Chomsky-Normalform mit
V = {S, A, B,C}, & = {a,b} und den folgenden Produktionen:

Sei w = baaba.

Folgende Tabelle entsteht durch Anwendung des CYK-Algorithmus. Z.B. bedeutet B €
V(3,5), dass aus der Variablen B das Teilwort w3w4ws = aba hergeleitet werden kann.

Tragen Sie in der Tabelle die drei fehlenden Einträge V(1,2), V(1,4) und V(1,5) ein. Wie
entnehmen Sie dieser Tabelle, dass w € L(G) ist?

S + AB|BC B+ CC|b

A— BAla

C — ABla

Seite: 6

b a a b a

Vd,1) V(2,2) VG3,3) V(4,4) V5,5)

{B} {A,C} {A,C} {B} {A,C}
va.) v2,3) V3) V(4,5)

{B} {S,C} ,

v1,3) V(2,4) v3,5)

@ {B} {B}
Vd) V(2,5)

{$,A,C}

VY1,5)