- Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl:

Herbst
Kennwort: 461 13

2004

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 2004 Einzelprüfungsnummer: 46113 Seite: 2

Thema Nr. 1

Sämtliche Teilaufgaben sind zu bearbeiten!

Teilaufgabe I

Gegeben sei der nicht-deterministische endliche Automat M mit dem Eingabealphabet > = {a,b} , der
Zustandsmenge Q = (09,999; } Anfangszustand go, Endzustand gq; und der Übergangsfunktion 5
mit: N
(4,4) {a},
(va) {a},
(4-5) {41.42},
(42.4) {9};

(4,6) {a},
(4.x) HO für alle übrigen (q,x) e Ox2.

L(M) sei die von M akzeptierte Sprache.

a) Beweisen oder widerlegen Sie:

al) aababb e L(M).

a2) Jedes w € L(M) enthält das Teilwort bb.

a3) Das dritte Zeichen jedes w € L(M) ist ein b.
a4) Das vorletzte Zeichen jedes w € L(M) ist ein b.

b) Geben Sie eine reguläre (Typ-3-) Grammatik an, die L(M) erzeugt.
c) Konstruieren Sie aus M einen deterministischen endlichen Automaten, der L(M) akzeptiert.

d) Geben Sie einen regulären Ausdruck an, der L(M) beschreibt.

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

Teilaufgabe 2

Die Sprache Z über dem Alphabet {a,b,c} sei gegeben durch L = {a‘bc’ |j > i > 0}.

a) Beweisen Sie: L ist nicht regular.
b) Die Grammatik G mit den Terminalzeichen a, b, c, den Variablen S, A, C und dem Startzeichen S
enthalte die Regeln
S — bC|aACc
A-...
C=...
Vervollständigen Sie die Regeln für A und C so, dass G die Sprache Z erzeugt!
c) Überführen Sie die Grammatik aus Teil b) in Chomsky-Normalform.
d) Ist die Sprache Z mit einer deterministischen Turing-Maschine mit einer Zeitkomplexitat O(n”)
entscheidbar (n ist die Länge der jeweiligen Eingabe)? Begründen Sie Ihre Antwort!
Teilaufgabe 3

Sei © ein Alphabet.

a)

b)

Was bedeutet es, dass eine totale Funktion f : 2° — X” mit einer Turing-Maschine berechenbar
ist?

Für fest gewählte u,v,,v, € 2" und eine totale Funktion g: 2° — "sei h: 5° + D
definiert durch

falls g(w) = u

h 2
(w) = v, sonst.

2

Beweisen Sie: Ist g mit einer Turing-Maschine berechenbar, so gilt dies auch für h.
Herbst 2004 Einzelprüfungsnummer: 46113 Seite: 4

Thema Nr. 2

1. Automatentheorie

Es sei bin(n) die Binärdarstellung der natürlichen Zahl n (ohne führende Nullen).
Weiter sei D = ,,, {bin(n): n € N und n= 5 (mod 8)}.

a) Geben Sie einen deterministischen endlichen Automaten an, der D akzeptiert!
b) Geben Sie einen regulären Ausdruck an, der D beschreibt!

2. Formale Sprachen

Es seien M= {wuw*v :w,u,ve€ {a,b} *} und N= {weuw*v :w,u,v € {a,b} *}.

Dabei sei das Zeichen c ¢ {a,b} und (a,a,...a,)" = 449.4,a, für alle a,,a,,...,a, € {a,b}.

a) Geben Sie kontextfreie Grammatiken an, die M und N erzeugen.
b) Sind M und N regulär? (Begründung!)

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

3. Endliche Automaten

Gegeben sei folgender nichtdeterministischer endlicher Automat A, .

3.1

3.2

3.3

3.4

A, = (2, x, 6, 9 {4%5})

2 {9,94}
x = {a,b,c}

5 = {(@,2),4,),((as4).4)>
((a,55);4,) s((a5)s4)s((a,»€)s 4)»
(a4), 4%) (444) 4%)s((4s€)%)}

Stellen Sie den Automaten A, graphisch dar!

Konstruieren Sie aus ‚A, einen per Konstruktion zu A, äquivalenten deterministischen endlichen Automaten A,! Stellen Sie den Automaten A, graphisch dar!

Welche Sprache wird von A, bzw. A, akzeptiert (ohne Beweis)? Beschreiben Sie die Sprache
durch einen regulären Ausdruck!

Geben Sie einen per Konstruktion minimalen und äquivalenten deterministischen endlichen Automaten Ain aus folgendem endlichen Automaten A,! Stellen Sie den Automaten A, in graphisch dar!

4,=[9,2.8,9.(4.))

9=[9.9,%,9,9)
Z={a,b,c}

6¢(Qxz)xQ,

5=(((o. a), 4). (40-5). 4s). (a0, c), 9).
(a. a),4,), (a. b), 42), (a. c), 4).
(a2, a),4,),((¢2, b), 43), (92, e), 44),
((4.2).9;). (9. 2).9).((.0).9).
((44.4), 45), (44,8), 4), ((4..0).4;)}

Fortsetzung nächste Seite!
Herbst 2004 Einzelprüfungsnummer: 46113 Seite; 6

ne

4. Turing-Maschinen

Eine deterministische Turingmaschine ist ein Tupel (2, 4,1, 5,q,, B, F). Dabei ist Q die endliche
Zustandsmenge, © das endliche Eingabealphabet, T das endliche Bandalphabet,
6:QxT—QxTx{Z,R,N} die Übergangsfunktion, q, der Startzustand, B das Blanksymbol und
F eine Menge von Endzuständen. Eine solche deterministische Turingmaschine liest also in jedem
Schritt das aktuelle Zeichen unter dem Schreib-/Lesekopf, entscheidet abhängig vom aktuellen Zustand und dem gelesenen Zeichen, welches neue Zeichen geschrieben, in welchen Folgezustand übergegangen und ob dabei der Schreib-/Lesekopf nach rechts (R), nach links (Z) oder gar nicht (N) bewegt werden soll.

Sei nun © = {a,0,1} und I’ = {a,0,1,B}. Konstruieren Sie eine Turingmaschine, welche eine Zahl
in Binärdarstellung inkrementiert. Beachten Sie dabei die folgenden Vorgaben:

Auf dem Band steht als Eingabe ein a und rechts davon die gegebene Zahl in Binärdarstellung mit
dem niederwertigsten Bit ganz rechts. Beispiel für die Dezimalzahl 13: BBBa1101BBBBB. Der
Schreib-/Lesekopf steht zu Beginn der Verarbeitung auf dem Zeichen a und soll auch am Ende wieder
auf diesem Zeichen a stehen. Das Zeichen a darf während einer ganzen Verarbeitung in keinem Fall
überschrieben werden! Es darf auch kein weiteres Zeichen a geschrieben werden.

Schreiben Sie die Übergangsfunktion 6 in Tabellenform nieder, pro Zustand eine Spalte, pro Zeile
ein Bandsymbol und dann in jeder Zelle den Folgezustand, das zu schreibende Zeichen sowie die

Kopfbewegung.