Prüfulgsteilaehter

prüfulgstermi!

ElnzelprüfuagsEu@ea

Keunzahl:

Frühjahr

66110

Kennwort:

r99s

Arbeitsplatz-lfr.

Erste

:

Staatsprüfung

für
-

Fach 3

ein

:

Anzahl

der

gestellten

Anzahl

der

Druckseiten

an öffentlichen
-

Prüfungsaufgaben

Informatik

Einzelprüfung

Lehrant

(vertieft

Automatentheorie

, Algorithn.

Themen (Aufgaben):
dieser

vorrage:

Bitte

studiert)

wenden !

1
I

spracheu

Schulen

Frühjahr

1995

Einzelprüfungsnr.

SEintliche Teilaufgaben

: 66110

Seite:

2

sind zu bearbeitent

AtrgPbe1
Gegebensei die Grammatft f, mit ta,b] ats Menge der Terminalzeichen,den Nichtterminalzeichen Z,A,B, dem A;<iomZ und den Produktionsregeln

.

Z-+eB
Z+bA
A-+e
A+tZ
B-rb
B+bZ

Die Grammatik f, entsteheaus I, dadurch,daß an diesenProduktionsregelnnoch die weiteren Regeln
A -+ bAA
B -+ aBB
hinzugenommenwerden.
Der jeweilige Sprachschatzvon f, und f, sei mit E(f1) bzw. .f(f2) bezeichnet. e bezeichne das leere Wort.
a)

BeweisenSie: .g(fr) = {ab,be}*\{r}.

b)

KonstnrierenSie direkt aus I, einennicht-deterministischenendlichenAutomaten,der
genaudie Zeichenreihenvon .g(ft) akzeptiert.KonstnrierenSie dann aus diesemAutomaten einen deterministischenendlichenAutomaten,der genaudie Zeichenreihenvon
Y(fr) akzeptiert.

c)

GebenSie eine (deterministische)TuringmaschineT an,die außereinem Leerzeichen
nur die Zeichen aus {a,b} verwendet und g(fr) in folgendem Sinne akzeptiert: Ein
Wort rpe {a,b}* steht auf dem ansonstenleeren Band. Angesetzt auf das erste Zeichen von ro (bart. auf ein Leerzeichen,falls rp das leere Wort ist), erreicht jn genau
dann nach endlich vielen Schritten einen Endzustand,wenn w e g(fr) ist.

'

d)

BeweisenSie: ambbebbba e .g(f2).

e)

Flir ein n, e ta,b)* entsteheF aus il,, indem man jedes a in p durch b gnd jedes b in nr
durch a ersetzt.
BeweisenSie: Ist w e 9(fr), so ist auchtre g(Ir).

f)

tjberfi.ihren Sie fz h Chomsky-Normalform.

Fortset,zung nächste Seite I

'Frühjahr

1995

Ej-nzelprüfungrsnr. : 66110

Seite:

3

Artrgabe2
NAT bezeichne den abstrakten Datenqp mit der Sorte nat der natlirlichen Zahlen (einschließlich 0) und den üblichen Operationerrauf nat. Der abstrakte Datentlp VEKTORsei
wie folgt defluiiert:
ebstrast ttp. VEKTOR
(* Alles, was NAT enthdlt, darf vernrendetwerden *)
uae! NAT
rorte vektor, index (* Die Sortenvon VEKTORr,)
funstiana null; + vektor,
proj: vektor x index-r nat,
sacc.'vektor x index-+vektor
ariomr Vx evektor Vf,j e index:
Wihutl"i) = 0,
proikucc(x,f),i) = proi(x,i) +1,
proißucc(x,i),j) = proj(x,j)
fi.ir i + I
endoftype
a)

Die Funktion f: nat x index+ vektor sei gegebendr.rchdie Funktionsvereinbanng
function/(hnat,f : index)vektor:
it k= 0 then null elae scc(fllr-l,i),i)

endif

Beweisen Sie unter Verwendungder Axiome von VEKTOR,daß für alle k e nat und
f,.1e indexgilt:
a1)
aD
b)

proi(f(k,i),i) = k
proif&,i),i)=0

flirf+j

Geben Sie in Analogie zur Funktionf in Teilaufgabea) eine rekursive Funktionwereinbarungfür eine Funktiong:vektorxnatxindex+vektor an, für die fi.ir alle kenat und
i,j e indexgilt:
b1)
b2)

proj(g(x,k,i),i) = proj(x,i) + k
proiGk,k,i),i) = proi(x,j) .fi.ir r+y

BeweisenSie bl) und b2) für lhre Lösung.
c)

Für ein fest vorgegebenes
ne[.[ sei nun index=tt lf eiN trnd lsisn] und vektor=
pie Funktionennullnproi und succ seiengegeben
fu
lsisn).
t(xr,...,x)lxreNo
durch
('T.Iuuvekto/'),
null = (0,0,..,0)
((xr,...,xr,),f)
=
proj
*r,
l,xs*1,...,x).
succ((x1,...,Ji),i)= (ir,...rxs-1,xs+
c1)

Zeigen Sie, daß die so definierten Funktionendie Axiome von VEKTORerflillen.

c2)

Objekte der Sorte vektor könnenin höherenProgramrniersprachen
als Reihungen
der Länge n realisiert werden (Typbezeichnungetwa üTay [t..n] sf nat). Geben
Sie (in der Notation einer derartigqnryogrammiersprache)
Algorithmen zur Realisierung der Funktionen null, pTpi und succ an.

c3)

Geben Sie (in einer Notation wie in Teilaufgabec2)) einen Algorithmus an, der
für (xr,...,*J,(y 1,...,!n)e vektor den "summenvektor"(x1*I1,...,xr,*IJ berechnet und dabei nur die Funktionen nuLl,proj und succ verwendet. Erläutern Sie
die wesentlichenSchritte des Algorithmusdurch geeigneteKommentare.

Fortsetzung

nächste Seite !

Frühjahr

Einzelprüfungsnr. : 66110

1995

Seite:

At'eÜe 3
Durch die Fr,nktionstrereinbanng
furtetiqr f(x,y,rtnat) nat :
It Z= 0 tfPn x+y
elae if Y=0 üen 1
efesfVk,yl,z),x,z-l)
endif

endif

ist eine Ftrnktion .f t No3- N0 definiert.' Ferner sei die Funktion g: No r h.Io+
[.lo mit

dx,y)

=i*
lc=O

gegeben.
a)

BestimmenSie f(3,4,1).

b)

Beweisen Sie: f(x,y,r1 terminiert für alle x,y,z € No.

c)

Geben Sie (in der Notation einer höheren Programmiersprache)unter
Verwendung
eines Kellers als zusätzlicher "Hilfs"-Datenstruktur einen iterativen
Algorithmus an,
der f(x,y,d für beliebige xl,z. No berechnet. Erläutern sie Idee
trnd wesentliche
Schritte lhrer Lösung.

d)

Beweisensie, daß fijr alre x,y€ No gilt: /(x,y,2) = g(x,y).

e)

BeweisenSie, daß die Funktiong sich unter ausschließlicherVerwendung
von Addition
und Multiplikarion (auf 0rlo)sowie primitiver Rekr.rsiondefinierenl?ißt.

4