‘Prifungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl: .

| Frühjahr

Kennwort: - 46 1 1 3
2007

Arbeitsplatz-Nr.: \

J

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!
Frühjahr 2007 Einzelprüfungsnummer: 46113 Seite: 2

Thema Nr. 1
Sämtliche Teilaufgaben sind zu bearbeiten!

Aufgabe 1:
(Automatentheorie) . BReREz

Gegeben seien die Sprachen

N

{abe #:i,jeN},
{ai Bici d :i,7EN},
{ai Bcd) 24,7 EN}.

i

iH

Ir
La
Ls

Für welche Sprache existiert ein endlicher Automat, der diese erkennt? Falls es einen solchen
Automaten gibt, geben Sie ihn an! Andernfalls begründen Sie die Nichtexistenz!

Aufgabe 2:
(Formale Sprachen)

Zeigen Sie, dass kontextfreie Sprachen nicht abgeschlossen bzgl. der Durchschnittsbildung sind!
Betrachten Sie hierzu

Ly {a" bP cs nym © N}
Lp = {a™ Uc: nme N}

N

Zeigen Sie, dass L, und L kontextfrei sind, nicht aber-Z, Le (Pumping Lemma).

Aufgabe 3:
(Berechenbarkeit und Komplexität)
Gegeben sei die Sprache L = {a" bc: n € N}.

a) Geben Sie ein Turing-Programm en, das für jedes w € {a, b,c}* entscheidet, ob w € L gilt
oder nicht. Beschreiben Sie jeden Schritt im Detail!

b) Welche Komplexität besitzt der Algorithmus?
Frühjahr 2007 .  Einzelprüfungsnummer: 46113 Seite: 3

Thema Nr. 2 .
| Sämtliche Teilaufgaben sind zu bearbeiten!

Aufgabe 1:
i (Automatentheorie)

Gegeben sei der folgende nichtdeterministische Automat N.

a) Geben Sie einen regulären Ausdruck für die von N erkannte Sprache an!

b) Wandeln Sie N in einen deterministischen endlichen Automaten D um! Gehen Sie dabei systematisch vor und beschreiben Sie jeden der Schritte!

Aufgabe 2:
(Formale Sprache)
Hinweis:
Eine Chomsky-Normalform ist eine kontextfreie Grammatik G mit e & L(G), welche nur Regeln
der Form
. A— BC
bzw. Aa
.. besitzt.

(A, B, C Variablen; a Terminsymbel)
a) Beweisen Sie: Wenn eine Grammatik G iri Chomsky-Normalform ist, dann wird ein Wort w
der Sprache L(G) in genau 2|w]| — 1 Ableitungsschritten erzeugt. .
b) Gegeben sei die folgende Grammatik für aussagenlogische Konjunktionen, die nur die Aussagenvariablen „A“ und „B“ enthalten.
Conj > Lit | Lit' N Con
Lit > Term |'-' Term
Term —! A’ {'B'
Beispiele, die mit dieser Grammatik generiert werden können, sind:
mA
B
AN.-B
AABAAAB

Wandeln Sie diese Grammatik in Chomsky-Normalform um!

Fortsetzung nächste Seite!
Frühjahr 2007 Einzelprüfungsnummer: 46113 Seite: 4

Aufgabe 3:
(Berechenbarkeit)

a) Definieren Sie den Begriff „rekursiv aufzählbar“ für Sprache A C 57*!
b) Zeigen Sie: Sind die Sprachen A und B rekursiv aufzählbar, so auch AUB und Ax B.

Aufgabe 4:
(Komplexität)

Der folgende Algorithmus (in Java) sortiert eine Reihung von ganzen Zahlen.

public static void selectionSort(int datal]) {
for (int i = 0; i < (data.length-1); it+) {
// Finde das Minimum
int minIndex = i;
for (int j = i+ 1;,4 < data.length; j++) {
' aif (data[j] < data(minIndex]) {
minIndex = j;

+
F
// Vertausche aktuelles Datum und Minimum
int tmp = datali];
data [i] = data [minIndex] ;
data (minIndex] = tmp;

Welche Zeitkomplexität hat selectionSort? Berechnen Sie genau die Anzahl der benötigten
Vergleiche und folgern Sie daraus die Komplexität in O-Notation!