Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl:

H t
Kennwort: ________ erbs 46 11 3

2007

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

Bitte wenden!
Herbst 2007 . Einzelprüfungsnummer: 46113 Seite: 2

Thema Nr. 1

Es sind alle Teilaufgaben zu bearbeiten!

Aufgabe 1_ (endliche Automaten)
Gegeben sei ein nichtdeterministischer endlicher Automat A, mit Zustandsmenge
Q = {A,B,C,D,E}, Eingabealphabet 5> = {0,1}, Startzustand A und Endzustandsmenge F = {EF}.

Die Übergangsfunktion 6: Q x DUfe} > P(Q) sei durch folgende Tabelle gegeben:

s\alslelol»
oI{c} | B | {A} | {2} | {D}
1) {C} | {B} | {D} | {A} | {E}
eliB}ı 9,98 JiB}| 9

Dabei bezeichne P(Q) die Potenzmenge von Q.

a)

b)

Zeichnen Sie den Automaten in Form eines Übergangsdiagramms, das für jeden Zustand einen
Knoten und Kanten zwischen den Knoten gemäß der Übergangsfunktion enthält. Markieren
Sie den Endzustand gesondert.

Konstruieren Sie mit Hilfe der Teilmengenkonstruktion einen zu Aı äquivalenten deterministischen endlichen Automaten Az. Erzeugen Sie dazu vom Startzustand von A, ausgehend
schrittweise die Zustände des deterministischen endlichen Automaten Az als Teilmengen der

. Zustände von Aı. Geben Sie die jeweils erzeugten Teilmengen an. Zeichnen Sie den so erhaltenen Automaten Ay als Übergangsdiagramm.

Identifizieren Sie äquivalente Zustände von Asa, indem Sie den Table-Filling-Algorithmus anwenden. Bauen Sie dazu schrittweise eine Tabelle auf, in der für die möglichen Zustandspaare
vermerkt ist, ob sie unterscheidbar sind. Begründen Sie die Schritte des Algorithmus.

Konstruieren Sie einen zu Aa äquivalenten deterministischen endlichen Automaten, der eine
minimale Anzahl von Zuständen enthält. Fassen Sie dazu alle äquivalenten Zustandspaare
von As zu jeweils einem Zustand zusammen. Zeichnen Sie den resultierenden Automaten als

_ Übergangsdiagramm.

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

Aufgabe 2:

(Wortproblem für kontextfreie Grammatiken)
Gegeben sei folgende kontextfreie Grammatik in Chomsky-Normalform:

G = ({A, B,C, S}, {a,b}, P,S)

mit Variablenmenge V = {A, B,C, S}, Alphabet 5~ = {a,b} und Startsymbol S. Die Produktionen P sind gegeben durch:

P={ S-AA|BC
A—BA|a
B-CB|b
C-AB|a }

a) Beweisen Sie, dass diese Grammatik mehrdeutig ist, d. h. dass es für mindestens ein Wort der
von G erzeugten Sprache mindestens zwei unterschiedliche Ableitungsbäume gibt.

b) Entscheiden Sie durch Anwendung des CY K-Algorithmus, ob das Wort w = baab von der
Grammatik G erzeugt wird. Konstruieren Sie dazu schrittweise eine Tabelle, deren Einträge
Xi alle Variablen der Grammatik enthält, die das Teilwort a;...a; des gegebenen Wortes
w= Qı...Q, erzeugen können. Geben Sie die zur Ermittlung jedes Eintrages erforderlichen
Berechnungen an und begründen Sie die Berechnungen.

Aufgabe 3:

(Berechenbarkeit und Turingmaschinen)

a) Konstruieren Sie eine determinstische Turingmaschine, die eine Eingabe x € {0,1}* als
Binärzahl interpretiert und zu x die Zahl 1 addiert. Beim Start. der Turingmaschine stehe
das Eingabewort x auf dem Eingabeband. Beschreiben Sie das Vorgehen und die Arbeitsweise der von Ihnen entworfenen Turingmaschine. Erläutern Sie die Rolle der Zustände der von
Ihnen entworfenen Turingmaschine und geben Sie die Übergangsfunktion in Tabellenform an.
Zeichnen Sie die Turingmaschine als Übergangsdiagramm.

b) Ilustrieren Sie die Arbeitsweise der von Ihnen konstruierten Turingmaschine, indem Sie die
Berechnungsschritte der Turingmaschine für die Eingabe 101 angeben. Verwenden Sie dazu
die Beschreibung durch Konfigurationsübergänge.

c) Turingmaschinen können dadurch erweitert werden, dass das Eingabeband in mehrere Spuren unterteilt wird. Geben Sie an, ob durch diese Erweiterung die Möglichkeit des Beschreibungsmechanismus erweitert wird, d. h. beantworten Sie die Frage, ob durch die Erweiterung
Sprachen erkannt werden können, die ohne die Erweiterung nicht erkannt werden können. Begründen Sie Ihre Antwort entweder dadurch, dass Sie eine solche Sprache angeben oder einen
Mechanismus skizzieren, der die Simulation von Turingmaschinen mit mehreren Spuren auf
eine Turingmaschine mit einer Spur durchführt.


Herbst 2007 Einzelprüfungsnummer: 46113 Seite: 4

Thema Nr. 2

Aufgabe 1:

(formale Sprache)

Sei L die Menge aller Worte über dem Alphabet {a,b},

deren zweites Zeichen (von links) ein a,
deren drittletztes Zeichen ein b ist und
bei denen nie zwei a’s aufeinander folgen.

Ist Z regulär oder kontext-frei und nicht regulär oder nicht kontextfrei?
Begründen Sie Ihre Antwort durch die Angabe einer passenden Grammatik oder eines Automaten.

Aufgabe 2:
(Abschlusseigenschaften)

Zeigen Sie:
i) Die regulären Sprachen sind abgeschlossen unter Durchschnitt.
ii) Die kontextfreien Sprachen sind nicht abgeschlossen unter Durchschnitt.

Begründen Sie Ihre Antwort bei Teilaufgabe i durch die Konstruktion eines entsprechenden Automaten bzw. einer Grammatik ohne den Beweis der Korrektheit ihrer Konstruktion.

Aufgabe 3: .
(kontextfreie Sprachen)

Definition:
Eine kontextfreie Grammatik G = (N,T, P, S), die nur Worte der Länge > 3 erzeugt,
ist in 3-Normalform, wenn die Produktionen die Form

A-BCB oder A-a haben

mit nicht-terminalen A, B,C, D und terminalen Zeichen a.
(Die 2-Normalform ist die Chomsky Normalform.)

Zeigen Sie:

Zu jeder kontextfreien Sprache L, die nur Worte x der Länge > 3 enthält, gibt es
eine kontextfreie Grammatik G in 3-Normalform, die L erzeugt.
Geben Sie die Konstruktion an. Der Äquivalenz- oder Korrektheitsbeweis ist nicht
verlangt. Hinweis: Sie dürfen die Chomsky Normalform verwenden.

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

Aufgabe 4 (NP-Vollständigkeit)

Das k-Färbbarkeitsproblem auf Graphen ist das Problem, ob man die Knoten eines Graphen G so mit höchstens k Farben färben kann, dass benachbarte Knoten verschiedene Farben
haben.

Warum ist das k-Färbbarkeitsproblem in NP?
(Es ist sogar bekannt, dass das k-Färbbarkeitsproblem NP-vollständig ist.)

Aufgabe 5 (Berechenbarkeit)

Was halten Sie von der These:
„Alles was exakt beschrieben werden kann, kann man auch berechnen.“

Geben Sie Argumente für oder gegen diese These an.