Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl:

Kennwort: _ Herbst - 4 6 1 1 3

Arbeitsplatz-Nr: _ 0. 2 0 1 3

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

Bitte wenden!

Herbst 2013 | Einzelprüfungsnummer 46113 Seite 2

Thema Nr. 1
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Aufgabe 1:
Reguläre Sprachen I

Sei = = {a,b} und Li die Sprache bestehend aus allen Wörtern gerader Länge über dem Alphabet,
%. Sei L2 die Sprache bestehend aus allen Wörtern über D, in denen b genau zweimal vorkommt.
a) Geben Sie jeweils einen regulären Ausdruck für Lı und L» an.

b) Eine Grammatik heißt rechtslinear, wenn es für jede Produktion Nichtterminale A,B und ein
Terminalsymbol x gibt, so dass die Produktion die Form A— zB oder A— e hat. Geben Sie
eine rechtslineare Grammatik für die Sprache LıNZy an. .

c) Geben Sie einen endlichen Automaten (gegebenenfalls mit e-Transitionen) an, der die Sprache
L{a(b*|c)*(a|b)) erkennt. :

Fortsetzung nächste Seite!

Herbst 2013 Einzelprüfungsnummer: 46113 Seite: 3

Aufgabe 2:
Reguläre Sprachen II

Sei 5 = {0,1}. Wir definieren die Inversion u von Wörtern u € D* wie folgt:
=e

:=19 für v € D*

1v :==0% für v € D*

“is

Für eine Sprache L C D* definieren wir
inverse_from(L) := {a,--- Gn | 3k. € Naı-- any mELAD<k<n}

die Sprache, die durch Invertieren der Wérter aus L ab beliebigen Positionen hervorgeht.

Beispiel: Ist L = {000, 11}, so ist inverse from(L) = {000, 001, 011, 111, 11, 10, 00}.

a) Sei L die Sprache, die durch den folgenden endlichen Automaten akzeptiert wird. Geben Sie
einen endlichen Automaten (gegebenenfalls mit c-Transitionen) für inverse_from(Z) an.
Hinweis: Starten Sie mit einem endlichen Automaten für L und fügen Sie zusätzliche Zustände
und Übergänge ein.

b) Zeigen Sie: Ist L C D* regulär, so ist inverse_from(LZ) ebenfalls eine reguläre Sprache.
Hinweis: Verallgemeinern Sie Ihre Konstruktion von Teilaufgabe 1.
Erläutern Sie Ihre Konstruktionsidee!

Fortsetzung nächste Seitel

Herbst 2013 Einzelprüfungsnummer 46113 \ Seite 4

Aufgabe 3:
Kontextfreie Sprachen

a) Geben Sie eine kontextfreie Grammatik für die folgende Sprache an:

L={a "ei" |0o<no<m<t}

b) Sei Gi = (N,21,R,$) mit Ni = {S,T}, Sı = {a,b,c,d} und P, bestehe aus den folgenden
Produktionen:
S3TaS|T TobScid

i) Zeigen Sie dabdc € L(G).

ii) Bringen Sie die Grammatik G, in Chomsky-Normalform.

Fortsetzung nächste Seite!

Herbst 2013 Einzelprüfungsnummer: 46113 u Seite: 5

Aufgabe 4:
Berechenbarkeit und Entscheidbarkeit

Sei & = {0,1}. Wir nehmen an, dass jedes w € U* eine Turingmaschine kodiert und bezeichnen
diese TM mit M,. Die von M, berechnete Funktion bezeichnen wir mit py.

a) Welche der folgenden Mengen sind entscheidbar? Begründen Sie kurz.
i) I :={we€Y* | es gibt eine Eingabe, für die M, das leere Wort, ausgibt}
ii) = [we2*|imeNmit v=r}
DD IL={wei|WweizeL(tt)ego,l(e=1}
b) Ist die folgende Funktion berechenbar? Begründen Sie kurz.

1 wenn 9,(01) = 10

h(w) =
tw) 0 sonst

c) Konstruieren Sie eine Turingmaschine M mit Eingabealphabet ©, die jedes Vorkommen von 1

im Eingabewort verdoppelt. Das heißt, M soll die folgende Funktion f : 2* — Z*. berechnen:

fe)=e fw)=1f(w) . F(0w) =Of(w)

Beschreiben Sie auch Ihre Konstruktionsidee!
‚Beispiel: Für die Eingabe 01101 soll M die’Ausgabe 01111011 liefern.

Fortsetzung nächste Seite!

Herbst 2013 Einzelprüfungsnummer: 46113 Seite: 6

Aufgabe 5:
Komplexitätstheorie

Wir betrachten das Problem, in einer Schulklasse Gruppenarbeit durchzuführen. ‚Es gibt mehrere
Arbeitsthemen; jedem Schüler wird ein Thema zugeordnet und alle Schüler mit dem gleichen
Thema arbeiten in einer Gruppe. Allerdings weiß man, dass wenn gewisse Teilgruppen von Schülern
vollständig einem Arbeitsthema zugeordnet sind, sie sich gegenseitig und somit die ganze Gruppe

stören. Man möchte durch eine geeignete Zuordnung von Schülern zu Arbeitsthemen sicherstellen,
dass keine Störungen auftreten.

Formal betrachtet definieren wir das Problem GRUPPENARBEIT wie folgt:

Gegeben: ($,T,A):
5 ...Menge von Schülern
T...störende Teilgruppen, 7 < P(5$)
A ....Menge der Arbeitsthemen

Problem: Existiert eine Zuordnung g : $ — A, sodass aus jeder störenden Teilgruppe mindestens
zwei Schüler unterschiedlichen Arbeitsthemen zugeordnet sind:

VWPeT: 3 €T: Ft ET: g(t) ¢ g(te)

a) Begründen Sie: GRUPPENARBEIT liegt in NP.

b) Geben Sie eine polynomielle Reduktion von 3-CoL auf GRUPPENARBEIT an. Begründen Sie
kurz die polynomielle Laufzeit und die Korrektheit und Vollständigkeit der Reduktion.
Hinweis: 3-CoL ist definiert als das Problem, für einen gegebenen Graphen (V, E) zu entschei- den, ob die Knoten V so nit drei Farben eingefärbt werden können, dass keine durch Kanten
in E benachbarte Knoten derselben Farbe zugeordnet sind.

c) Zeigen Sie: GRUPPENARBEIT ist NP-vollständig.
Hinweis: Sie dürfen verwenden, dass 3-CoL NP-hart ist.

Herbst 2013 Einzelprüfungsnummer 46113 Seite 7

Thema Nr. 2
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Teilaufgabe I: Minimierung und Äquivalenzen Gegeben ist folgender deterministische endliche Automat (DEA) A über dem Alphabet & = {a,b}.

2) Konstruieren Sie den zugehörigen Minimalautomaten und dokumentieren Sie Ihre Schritte

auf geeignete Weise.
b) Geben Sie L(4) als regulären Ausdruck an.
c) Geben Sie reguläre Ausdrücke für die Äquivalenzklassen der Myhill-Nerode Äquivalenzrelation ~z(4) an. Erinnerung: Diese Klassen entsprechen den Zuständen des Minimalautomaten.
d) Sei B = (Z,2,6,20,E) der von Ihnen konstruierte Minimalautomat. Wir definieren die
Beobachtungsgleichheit ~g auf 5* durch uxgu< > Vz € Ziölz,u) = öfz,v).
Sollten Sie die vorhergehenden Aufgaben nicht gelöst haben, so nehmen Sie für B einen DEA
Ihrer Wahl mit L(B) = (a | b)b*a(a | b)b*. Bitte vermerken Sie dann, dass Sie diese Option
gewählt haben und geben Sie Ihren DEA B explizit an. ,

— Begründen Sie, dass ~g eine Äquivalenzrelation ist.

— Geben Sie zwei verschiedene Wörter an, die in derselben &g-Rlasse liegen.

Geben Sie zwei Wörter an, die in unterschiedlichen Klassen liegen.

Begründen Sie, dass g nur endlich viele Klassen hat.

Fortsetzung nächste Seite!

a)

b)

Herbst 2013 Einzelprüfungsnummer 46113 Seite 8

Teilaufgabe II: Berechenbarkeit Bekanntlich ist das Halteproblem Hy definiert als die Menge
aller Codes von Ainineumeerlinen, die bei leerer Eingabe halten. LZ.: Hy = {e | M.{e) hält}.

Begründen Sie, dass Ho rekursiv aufzählbar (= semi-entscheidbar) ist, das Komplement
Hy =N\ Ho aber nicht.

b) ° Eine Turingmaschine M kann man effektiv zu einer anderen Maschine tr(M) umbauen,

sodass gilt: tr(.M) hält bei Eingabe £ € N, genau dann, wenn’ M bei leerer Eingabe mindestens
t Schritte rechnet. Begrindey: Sie dies.

c) Essei Tot={e| M, hält für alle Eingaben x € N} das Totalitätsproblem.
Welche der folgenden Aussagen sind richtig? Begründen Sie jeweils Ihre Antwort!

— Die Konstruktion tr liefert eine Reduktion Ho < Tot.
. — Die Konstruktion tr liefert eine Reduktion. Tot < Ho.

— Die Konstruktion tr liefert eine Reduktion Tot< Ho.

— Das Problem Tot ist semi-entscheidbar.

— Das Problem Tot ist nicht rekursiv aufzählbar.

Teilaufgabe III: Komplexität Beim Problem MAX2SAT ist eine Menge von Zweierklauseln
und eine Zahl k € N gegeben. Gefragt ist, ob eine Variablenbelesung existiert, die mindestens
k von den Zweierklauseln erfüllt. Erinnerung: Zweierklausel: Disjunktion zweier Literale; Literal:
negierte oder nichtnegierte aussagenlogische Variable.

Ist zum Beispiel C = {X V.AY,¥Y V7Z, ZV 7X, X VY-Xv-Y}, so ist C,k = 4 eine positive
Instanz von MAX2SAT, C,k = 5 aber eine negative Instanz.

Beim Problem CLIQUE hingegen ist ein ungerichteter Graph G = (V,E) und JE N gegeben
und es ist gefragt, ob es in G mindestens j paarweise verbundene Knoten gibt (eine Clique der
Größe 5). Das Problem CLIQUE ist bekanntlich NP-vollständig.

Hat man einen ungerichteten Graphen G = (V, E) gegeben, so konstruiert man eine Menge von
Zweierklauselu wie folst: Variablen sind die Knoten von G. Für je zwei Knoten v,v’ mit (vv) €E
gibt man eine Klausel -v V —v’ aus und außerdem für jedes v» € V die Klausel v V v. Insgesamt
also |/| +. d Klauseln, wobei d die Zahl der Nicht-Kanten in G ist.

Begründen Sie folgendes: Hat G eine Clique der Größe 5, so kanhı man mindestens d +5 viele
dieser Klauseln simultan erfüllen.

Es gilt auch die Umkehrung dieser Aussage (können irgend d+ j der Klauseln simultan erfüllt
werden, so hat C eine Clique der Größe j), das dürfen Sie im folgenden ohne Begründung voraussetzen.

Was kann aus dieser Konstruktion nun gefolgert werden? Begründen Sie jeweils Ihre Antwort:

- Diese Konstruktion liefert eine Reduktion CLIQUE'<, MAX2SAT.
- Diese Konstruktion liefert eine Reduktion MAX2SAT <, CLIQUE.

- Die Konstruktion liefert ein Entscheidungsverfahren für MAX2SAT mit polynomieller Lauf
zeit.

* MAX2SAT ist NP-vollständig.