Prüfungsteilnehmer Prüfungstermin Einze üfungsnummer

Kennzahl:

Frühjahr 66110
1997

Kennwort:

Arbeitsplatz-Nr.:

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

- Prüfungsaufgaben -
Fach: Informatik (vertieft studiert)
Einzelprüfung: Automatentheorie,Algorithm. Sprachen

Anzahl der gestellten Themen (Aufgaben): 1

Anzahl der Druckseiten dieser Vorlage: 2

Sämtliche Teilaufgaben sind zu bearbeiten!

1. Automatentheorie und Formale Sprachen
Zu jedem nichtdeterministischen endlichen Automaten (NFA) A kann man einen deterministischenendlichen Automaten (DFA) A’ konstruieren, der die gleiche Sprache
akzeptiert, d.h. L(A) = L(A’).
(a) Geben Sie ein Verfahren für die Konstruktion von A’ aus A detailliert an!
(b) Für das Alphabet © = {u,5} und natürliche Zahlen n seien Sprachen L, und
R,„ definiert durch

Laie D"-b- 0" , Rn:=8*-b-2°

Geben Sie NFAs L, bzw. R„ an, welche L„ bzw. R,„ akzeptieren!
(c) Konstruieren Sie in den Fällen n = 0, 1,2 die zugehörigen DFAs £[,, und R}.
(d) Zeigen Sie, dass der minimale DFA, der L,„ akzeptiert, n + 3 Zustände hat.
(e) Zeigen Sie, dass der minimale DFA, der R„ akzeptiert, 2"*! Zustände hat.

Fortsetzung nächste Seite!

Frühjahr 1997 Einzelprifungsnr.: 66110 Seite: 2

2. Berechenbarkeit

Zu den klassischen Problemen in der Theorie der Berechenbarkeit zählt das sog.
“Korrespondenzproblem von POST" (PCP).

(a) Formulieren Sie die Problemstellung des PCP.

(b) Das PCP ist algorithmisch unentscheidbar. Begründen Sie dies!

(c) Die Unentscheidbarkeit des PCP kann dazu verwendet werden, mittels Reduktion die Unentscheidbarkeit von Problemen im Bereich der kontextfreien Grammatiken und Sprachen nachzuweisen. Geben Sie ein konkretes Beispiel hierfür an
(Problemstellung und Reduktion)!

3. Algorithmische Sprachen

Zwei bekannte Analysealgorithmen für allgemeine kontextfreie Sprachen sind mit
den Namen Cooke/YounGer/Kasami (CYK) und EaRLey verbunden.

(a) Erläutern Sie die Vorgehensweise bei beiden Algorithmen in ihren Grundzügen.

(b) Welche Aussagen über die Laufzeitkomplexität (evtl. auch für Teilfamilien der
Familie aller kontextfreien Sprachen) sind Ihnen bekannt?

(c) Stellen Sie einen der beiden Algorithmen detailliert dar (z.B. in Pseudocode),
begründen Sie dessen Korrektheit und Laufzeitkomplexität.

4. Programmiermethodik, Effiziente Algorithmen

Eine der grundlegenden Aufgabenstellungen der Algorithmik ist die Identifizierung
und Klassifikation von Problemen, für die es effiziente Entscheidungsalgorithmen
bzw. effiziente Verifikationsalgorithmen gibt. Die entsprechenden Problemklassen
werden mit P bzw. NP bezeichnet.

(2) Geben Sie Definitionen für die Klassen P und NP an und erläutern Sie diese
an Beispielen.

(b) Erläutern Sie, in welchem Sinne die o.g. Klassen “robust” gegenüber definitorischen Variationen sind.

(c) Was versteht man unter der P-vs.-VP-Problematik?

(d) Beschreiben Sie das Reduktionskonzept innerhalb der Klasse NP an einem
Beispiel.

(e) Was sind und welche Bedeutung haben A’P-vollständige Probleme? Erläutern
Sie diese Begriffsbildung und geben Sie Beispiele für solche Probleme an.

(f) Betrachten Sie das Problem, bei dem man danach fragt, ob eine vorgelegte
aussagenlogische Formel eine Tautologie ist. d.h. ob sie unter allen Belegungen
der in ihr vorkommenden Aussagenvariablen mit Wahrheitswerten “wahr” bzw.
“falsch” den Wert "wahr” annimmt.

Diskutieren Sie den Status dieses Problems in Bezug auf die Problemklassen P
und A’P.