Prüfungsteilnehmer

_

hüfungstermin

Einzelprüfungsnurnmer

Kennzahl:

Herbst
Kennwort:

1998

66IT2

Arbeitsplatz-Nr.:

Erste Staatsprüfungfür ein Lehramt an öffentlichen Schulen
PrüfungsaufgabenFach:

Informatik (vertieft studiert)

Einzelprüfung:

Automatentheorie,Komplexität,Algorith.

Anzahlder gestelltenThemen(Aufgaben): z
Anzahlder DruckseitendieserVorlage:

8

Bitte wenden!

Herbst1998

Einzelprüfungsnunmer
: 66Ilz

Seite:2

Thema Nr. 1
Sämtliche Teilaufgaben sind zu bearbeiten!
L Gramnatiken und Automaren
Sg"Je-sche
Ausdrilcke BA_alsSpracheüber L+ mit L =
YT ydl",t
{0, l, x, y, +, _,C )} darstellen.
Dabeistehen0,1 filr die BooleschenKonsä."n,
*, y Äir-so_otesche
va;abl;; ; fää
Disjunktionszeichenund ein vorausgestelltes- für die Nelation.
oa"
roopoltion
z"i"nerüäweggerassen'Die Klammern "(" und ')u könnenwegg"t*-r* *"ra"o,
arrr ri. *"g", a", n"gä, außai"
Konjunktion stärkerbindet als die Disj'rGän oJer wegen
aer assoziativgesetzetibirfltrsig sind.
Unter verwendung der genanntenSymbolesollendie Booleschen
Ausdr{lckenachden folgenden
Regelnaufgebautwerden:
i)
ii)
üi)
iv)

Literale sind BoolescheKonstantenund variablen. Ein
negiertesLiteral ist auchein Literal.
Nichts sonstist ein Literal. Beispiel: _ _- 0
schreibt man zwei Be hintereiaaurder,
so erhärtman eineKonjunrtion. Beispiel: x- l xy0,
,
0y-lx.
JederBA ist eine (tiviale) Disjunktion. Die Summezweier
Disjunktionenist wieder eine
Disjunktion.Beispiel:x-1, x+1, y+-x+0.
JedesLiteral'nd jede Konjunktion ist ein BA. Jedeeingeklarnmerte
Disjunltion ist ein BA.

a) GebenSie eine kontextfrei?.gry-Iit
2) für die obendefiniertenBA an und
tChonrslcy_Typ
leiten sie die beidenAusdrticke Ox-ry und
-it
nire Ihrer c*--"til.
11o.9y-*j
"t
b) BeweisenSie die folgendeAussage:
Ersetztman in der Sprache(bzw. äer in AufgabeI konstuierten
Grammatik)alle Termrnalzeichenbis auf die Klammem
durchdasleereWort e, dannist die so erhalteneSprache
immer noch nicht regulär.
Nun definierenwir mit den obigenGesetzeneineanderesprache
BA*, indem wir i), i1), ig beibe_
haltenund iii) folgendermaßenverändem:
iii)*

JedesLiteral ist eine (tiviale) Disjunktion. Die surnmezweier Disjgnktionen
ist wieder
eineDisj unktion.

c) stellen sie eine Grammatik auf, die BA* erzeugtund leiten Sie
damit die Ausdrrlcke(0)(x) rmd
(l+x+y) ab.
d) zeiger, Sie, dassBA* regulär (vom chomsky-Typ
3) ist, indem sie einen endrichenAutomaten
angeben,der BA* erkennt.
e) Nun vereinfachenwir die
Ba ar1,Teilaufgabea) zu BA', indem wir als einzigesLiteral
fnnltre
dasZeichen/ zulassen.Geben
Sie einenKellerautö*ut"o *, der die spracheBaiorcr-,.

FortsetzungnächsteSeite!

Herbst1998

Einzelprüfungsnummer:
66ILz

Seite:3

2. Turingmaschinen und Berechenbarkeit
Wir betrachteneine TuringmaschineT : (I, B,
Q, ö, qo),wobei I : {0, 1} das Eingabealphabet,B :
I v {#} das Bandalphabetmit dem Leerzeichen#, :
Q {qo, .. ,Qo}eine Menge von Zusfänden,ö Q"B+QxBx{<-,ü,*}dieZustandsübergangsfunktionundqederAnfangszustandist.
Die Zeichen +- bzvv- + symbolisieren eine Bewegung des Schreib-/ Lesekopfes (nach der
aktuellen Operation)nach lint$ bzur.rechts.Die Maschinehält nach der aktuellen Operation.wenn
die
Zustandsübergangsfunkion nicht definiert ist oder auf ein J ninrt.
AIs Eingabewörterlassenwir nur Zeichenfolgen der Form 0n10'mit n, m €N6 zu, wobei 0n für
eine Zeichenkefieaus nNullen stehe.Am Anfang steheder Schreib-ll.esekopf auf dem ersten(linken) Zeichen des Eingabewortes. Links und rechts vom Eingabewort stehenausschließlich Leerzeichen auf dem Band.
Die Werte der Zustands-Übergangsfi:nktionö(q, b) seiendurch die folgende Tabelle definiert:
Bandzeichenb e B
0
1
Zustandq€ Q

9o

(qs,#, +)
(qr, l, +)
(qr, 1, -+)

(q6,#, ü)
nicht definiert

Qt

(qr,o,+)

9z
9q

(qg,1, r-)
(ql, o, e)
(qq,o, e)

(q:, l, <-)
(q+,#, +-)

9s

(qs,#, -+)

(q+,#, <-)
(qo,#, -+)
(q6,o, ü)

(qs,#, -+)

(q6,#, ü)

9l

a)

(qr,#, -+)

BeschreibenSie die vollständigeBerechnungvon T fürdas Eingabewort0010, indem Sie für
jeden Berechnungsschrittdenjeweiligen Maschinenzustandund die jeweilige Bandbelegung
angeben.

b) Stellen Sie die Arbeitsweise der Maschine T mit Hilfe einesgeeignetenZustandsübergangsdiagramms dar.
c) Die zulässigenEingabewörter 0nI 0* sollen nun jeweils ein Paarnahirlicher Za6len(m, n) repräsentieren.Welche Funktion f: No x No -+ No wird von T berechnet? Begrtinden Sie Ihre
Aussage

d) UntersuchenSie, ob Ihre in Teilaufgabec) angegebeneFunktion primitiv rekursiv ist und beweisen Sie Ihre Aussage.
e) Geben Sie eine möglichst kleine obere Schrankefür die Anzatrl der Berechnungsschrittevon T

flir ein zuiässigesEingabewort der Länge lwl : k an,

FortsetzungnächsteSeite!

Herbst1998

Einzelprüfungsnummer:
66Itz

Seite:4

3. Spezifikation und Implementierung
Gegebensei die folgende spezifikation der natürlichen zahlen

NAT - based_on BOOL
sorts nat
ops 0 :
nat
nat + nat
p:
nat -+ nat
*:
nat x nat -+ nat
zero: nat -+ bool
S:

axioms
nat generated_by 0, s

p(o): o

p(s(x)) - x
0+y:Y
s(x)+y:s(x+y)
zero(0) : True
zero(s(x))- False
Dabei bedeutetbased-on BOOL, dafJNAT auf einer geeignetenSpezifikation von BOOL aufbaut.
Die Aussage nat generated-by 0,s drückt aus, dafJalle Elemente aus nat als Terme der Forrn
s(s(..(0)..))dargestelltwerden können.
a) Nun soll die Spezifikation NAT in einer funktionalen ProgrammierspracheIhrer Wahl implementiert werden, wobei natürliche Zah\enals Bitlisten, das heißt als SequeruenBooleschei
Werte vom Typ [bool] dargestelltwerden sollen. ProgrammierenSie die dazu nötigen Funktionen.
b) Geben Sie eine Abstraktionsfunktion phi: pooll + Nat an, die jede Bitliste, die sich mit Hilfe
Ihrer Implementierung erzeugenläf3t,auf die dazugehörigenatürlich e ZahI abbildet. Mit Nat ist
dabei die Sorte gemeint, die in der von Ihnen gewäihltenProgrammiersprachedie natürlichen
ZabJenbzw. eine geeiguete obermenge davon implementiert.

5Herbst1998

Einzelpnifungsnumm
er: 66I12

Seite:5

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

1. a) Gegebensei die GrammatikG mit {1,2,a,b} als Menge der Terminalzeichen,der Variablen
S, der StartvariablenS und den produktionen
S + lSab, S -+ lab, S -+ 2Sbbb, S -+ 2bbb.
Sei L : L(G) die von G erzeugteSprache,w, : ab und w, : bbb.
A. BeweisenSie L (G) : {i1 ... ik w* ... w;r I i1 ... ik e { 1,2}).
B. Konstruieren Sie einen deterministischenKeller-Automaten, der L ah,zeptiert.
C. Ist L regulär? (Begründung)
b) Beweisenoder widerlegenSie für betiebigesprachenL, , L.,:
A. (Lt U Lr)* : L,* U Lr*
B. (L'*)* : L,*
2 . B e w e i s e n S i eI s: t f : N - + N L o o P - b e r e c h e n b a r s, o i s t a u c hs : N + N m i t

= i r,
e(n)
i = l

LooP-berechenbar.
3. Z2Yettreter aus siebenStaatenbesucheneine internationaleKonferenz. Welche der foleenden
Aussagenmuss wahr sein?(Begründung)
a) SechsStaatenhabenjeweils drei Vertreter und der 7. Staathat vier Vertreter.
b) Kein Staathat mehr als vier Vertreter.
c) Mindestensein Staathat vier oder mehr vertreter.
d) Kein Staathat weniger als zwei Vertreter.

FortsetzungnächsteSeite!

Herbst1998

Einzelprüfungsnumm
er: 66LL2

Seite:6

4. a) (Aussagenlogik)
A. BeweisenSie: " (A -+ B) <+ (--A v B) " ist eine Tautologie.
B. BegründenSie die Aussage:

o "Aus(F,G) folgtH. " ist äquivalent
zu " {F,G,-H} ist unerftillbar."
C. Beweisen
Siemit demResolutionskallcil:
. { - A v B , - B v C , A , - C } i s tu n e r f ü l l b a r .
D. BeweisenSie (unterVerwendung
der Teilaufgaben
A., B. und C.):
o " A u s{ A + B , B + C } f o l g t A+ C . , ,
b. (Prädikatenlogik)
Gegebenisr die folgendeFormel:
o f : ((Vx 3y P(x,y)) -+ ( 3x Vy p(x, y)))
A. Ist F allgemeingülrig?
B. Ist F erfrillbar?
C. FallsF ein Modellhat, gebenSieein solchesan.
5. a) StellenSiesichvor, Siestartenfür jededer folgenden
Teilaufgaben
denSCHEMEInterpretererneutund gebendie folgendenAusdrückeein. GebenSie für jede Teilaufgabe
dasErgebnisder AuswerfungdesletztenAusdrucksan.
i)

ii)
iii)

(define zwei 2)
(define drei 3)
(define eins 8)
(defineplus +)
(define kleiner ( )
(kleiner eins (plus zwei drei))
(cons 'a (cons 'b (cons (cdr (cons (cons 'd i) (cons ,c 2))) '0)))
(define (rek a)
(cond ((: a 0) 5)
((: a 5) (* 2 (rek (- a 5))))
(else (iambda (x) (rek (- x 5))))))
((rek (rek 5)) (rek 5))

FortsetzungnächsteSeitel

Herbst1998

Einzelprüfungsnumm
er: 66LIZ

Seite:7

b) Definieren Sie in einer funktionalenSpracheIhrer Watrl eineFunktion, die das Skalarprodukt
zweier Vektoren berechnet,die in rechtwinkligenKoordinatengegebensind. Die Vektoren
sollen als Listen repräsentiertsein. Sie könnendavonausgehen,dassIhre Funlrion nur mit
Vektorenaufgerufenwird, die gleichlangsind.
, (1 2 3) ,(2
Beispielin SCHEME: (skalarprodukt
2 2)) liefert 12.
6. Ein geordneterbinärer Baum ist entwederein leerer Baumoder bestehtauseiner Wurzel und
zwei binären Bäumenals linkem und rechtemUnterbaum.Dabei sind die Knotendes Baumsso
geordnet,dassfür alle Knoten o' im linken Unterbaumund für alle Knoten u, im rechtenUnterbaumvon Knotenu gilt:
u '3 u a u "
In SCHEME werdenBäumedurch Listen kodiert. Der folgendeBaum
T7

4

8

2

r

1

0

\
2

5

I4
hat die Listendarstellung:

'(17(8 (4
O O)

(10(eo o)

( 1 40 ( ) ) ) )

( 2 r( )
(2s( ) ( ))))

a) Definieren Sie in einer funktionalen SpracheIhrer Wahl die folgendenFunktionen:

{c
{<
*
ät
{<

rootliefert den Wert an der Wurzel des Baumes.
left -branctr
liefert den linken Teilbaum der Wurzel.
right-branch
liefert den rechtenTeilbaum der Wurzel.
make-tree
bildet aus einer Wurzel und zwei Bäumeneinen neuenBaum.
Der leere Baum sei als leere Liste definiert. Definieren Sie die Funktion emprytree?,die abfragt, ob ein Baum leer ist.

b) Definieren Sie die Funktion contains?,
die als Argumente einen binären Baum und ein Element
nimmt und überpnift, ob das Element im Baum enthaltenist.
c) Definieren Sie die Funktion insert,die als Argumente einen binären Baum und ein Element
nimmt und das Element an der richtigen Stelle im Baum einsortiert.

FortsetzungnächsteSeite!

Herbst1998

Einzelprüfungsnumm
er: 66I12

Seite: 8

7. Für Ihr örtliches Rathaussollen Sie eine Datenbankentwerfen,die personenbezogene
Daten zu
jedem Einwohner Ihrer Stadtspeichert.Zu jedem Einwohnerund jeder Einwohnerin werdendie
personenbezogenen
Daten gespeichert,die auf seinembzw. ihrem Personalausweis
vermerll
sind. Diese sind eine g-stelligePersonalausweisnummer,
Vor- und Nachnameder Person,Geburtsdatum,Geburtsort,Staatsangehörigkeit,
Ablaufdatumder Gültigkeit, wohnort, Augenfarbe
und Größe.
a) Definieren Sie mit den Mitteln einerbeliebigenimperativenPrograrnmierspracfue
(2.B. C)
zunächsteinen geeignetenDatentyppers-Daten,
der die obengenanntenInformationenaufnehmensoll. Sie könnendabeidavonausgehen,dasskein Orts- oder Personenname
länger
als 40 Zeichenist.
b) Sie wollen die Personennun in Stadtteilkarteienzusammenstellen.
Ein Stadtteilbestehtaus
einer konstantenmaximalenAnzahl von Einwohnern.Definieren Sie mit den Mitteln der gewlihlten Programmmiersprache
zunächsteine KonstanteMAXANZAHL mit dem Wert
12000.kgen Sieanschließend
einenDatentypsradtreil
fest, der einefeste,vorherbekannte
Anzahl von Einwohnem, nürnlich MAXANZAHL, vom Typ pers_Daten
auftrehmensoll.