prüfungstenia

Prüfuagsteilaehner

Einzelprüfulgsnumer

Kennzahl:

Herbst

66110

Kennwort:

r994
Arbeitsplatz-lilr.

Erste

:

Staatsprüfung

für

ein Lehramt an öffentliehen

, Prüfungsaufgaben

Fach:

Infomatik

Einzelprüfung:

Automatentheorie,

Anzahl der gestellten
Anzahl der Dnrckseiten

(vertieft

studiert

Algorithn.

tbemen (Aufgaben):
dieser

Vorlage:

Bitte

-

wencien !'

1
{

)
sprachen

Schulen

Herbst

L994

Einzelprüfungfsnr. 3 56110

Seite:

2

rr
I

Säntliche

Aufgaben

sind

zu bearbeiten!

At'epbc I
M sei die Menge aller Zeichenreihenüber dem Alphabet tO,l], die mindestensso viele
Zeichen I wie Zeichen O enthalten.
Geben Sie eine (deterministische) TuringmaschineT ur, dis arrßs1einem Leerzeichen nur
die Zeichen aus {0,1} venn'endetund M nfolgendem Sinneakzeptiert:Ein Wort n, e {0,1}*
steht auf dem ansonsten leeren Band! Angesetzt auf das erste Zeichen von rr (bznr. auf
ein Leerzeichen, falls rr das leere Wort ist), erreicht I genau dann nach endlich vielen
Schritten einen Endzust&d, wenn p e M ist.

Adgabc 2
Gegebensei die Gramrnatk lr mit {.,b} .als Menge der Terminalzeichen,den Nichtterminalzeichen ZA,B, dem Axiom. Z und den produktionsregeln
Z+tA
A-+b
A-+bB
B-+e
B-+b
B-+bB

'

,
Die Gr-arnmatikf2 entstehe aus I, dadurch,da$ zu diesen Produktiornregelnnoch die weitere Regel
B-+BA
hinzugenommenwird.
Der jeweilige Sprachschatzvon l, und I, sei mit 9(f1) bzut.9(f)bezeichner.
a)

BeweiseS
n ie: .f(fl) = (ebtlneD,f) u{rbntlneD.l}.

b)

Geben Sie einen deterministischen endlichen Automaten an, der genar die Zeicfrenreihen von g(f1) akzeptiert.

c)

BeweisenSie: 12 ist mehrdeutig.

d)

BeweisenSie: E(ft) + 9(Iz).

e)

lJberfütren Sie le h Greibach-Normalform

Aftüo

3

Sei int die Mengeder ganzenzahlenund rr$ int die Mengealhr endlichenFolgenganzcr
Zahlen.Für aaquint seien als Grundoperationen
ncrfrigbr:
-

Fortsetzung

nächste

Seitet

Herbst

L994

Einzelprüfungsnr. : 66110

em@i -+roqu int,
isenpty: tegu int -+boolean,,,
first: rcqu int -r intr
resti tcgu int + tcqu int,
prefrxi in! x r.qu int + rrqu int,

Seite:

emPtY= leere Folge
isempty(s)= tnte öc s ist leer

frst: (sr,...,sJ- s,
rest: (s'sr...Jr,) - (s2,...rsJ

preftx:(r,(s,;...,sJ).* (x,sr,...,sJ

(für s = emptysind/trsr(s) r,'rdresr(s)
nicht definierr.)
St sei die Menge aller Folgen aus ..qu iät mit einer durch
3 teilbaren AnzaSl rrcn Komponenten.
a)

Geben Sie (unter ausschließlicherVerwendungder genanntenGlgrdoperationen)
rekursive Funktioruvereinban[rgenan für Funktionen lnst, l.ead,,postfix,
conc mit folgender
Bedeutung (tasr(s) vd Lead(s)sina nur für s+ emptydefiniert):
lnst: rcqu int .+ intr
bad: ."qu int -r tcqu int,
postftx: lcqu int x int .r rcqu int,
conci raqu int x l|qu int -+roqu int,

b)

last: (sr,...,s) - s'
Iead,:("j,..."11,sr,i'- (sr,...,srr-r)
postfix:itrr,...,"j,x) ,. ("r,...ir,,*)
conc:((sr,...,s) ,(t1r...rt^))* ("r,...1srrrf1,..
.rt^)

Gegebensei die Funktion vorrt durch die Funktionsvereinbanng
fursüqr uorz(s:tequ int)requ int:
(* definiert nur itir s e S, *)
tt isempOr(s)tlnn s
olrr preffifirst(s), vonr(rest(Iead(read(i)))) mar
BeweisenSie: Frirs;S, ist yorn(s)das,,vordereDrittel von.C,,
d.h. für g=(s1,...,s1J,
k e IN6,ist yorz(s) = (s1r...,s1).

c)

Geben Sie analog zlrtrFunktion vorn'aus Teilaufgabe b) eine
rekursive Funktioffvereinban[rg füileine Funktion hinten an, die nur die genannten
Gnsrdoperationenund
Funktionen aus Teilaufgabe a) venrrendetund die für e
s ^g, das hintere Drittel von s
berechnet(d.h. hiten(s) =.(s2r.1,...,sgJfür s= (s1,...rs3 ke
D.,lg).
),
d) Geben Sie eine rekursive t rr*,torr*ereinbanrng
für eine Funktion mixean, die außer
den genanntencrtrndoperationenund den Funktionenaus Teilaufgabe ""ssshlie8lich
a)
die Ftrnktion vorn aus Teilaufgabe b) verwenden darf und
die füt " e S, das mitttere
Drittel von s berechnet(d.h. miuf$= (s1r1,...,s2Jfür s= (s1r...,s3
), ki *d.
e) Die relcursiveFunktionsvereinbanngvon yorn in Teilaufgabe
b) soll in qlstematischer
-in
Weise
einen iterativen Algorithmus (mit gleicher wirhnd überfi.itrrt werden (der
ebenfalls nur die angegebenenC'rundoperationenund Fgnktionen.
aus Teiladg;"
"l
verwendet)' Betten Sie dazv vorn in einen geeignetrn
altgemeinerenrepe$tiiekursiven Algorithmus ein, und entrekursivierenund spezialisiercn
Sie diesen ar deur gesuchten iterativen Algorithmus.
'rrograrnmiersprachen
objekte aus Lqu int können in
wie pAscAL, MoDuI-A o.ä. als
lineare Listen realisiert werden. Geben Sie (in einer deranigen programmienprache)
entsprechendeTlpvereinbanrngen trnd Algonithmenar Reatisierung
der angegebenen
Grundoperationenan.

Fortsetzung

nächste Seite !

3

HerDst 1994

g)

Einzelprüfungsnr.

: 66110

Seite:

4

.,

Geben Sie (in PA,SCAL,MODUI-A o.ä.) einen iterativen Algorithmus lautgean, der
unter Verwendungder Reallsierungender Crnndoperationengemäß Teilartrgabe 0 die
Anzahl der Komponenteneiner als lineare Liste realisierten Folge aus r.qu int berechngt.

Afgabe 4
Durch die Funktioruvereinbanng
'
funstlon f\*,y,zrnat)nat:
lf r=I+1 üln 3+y dre f(x*y*1,2r(y*1), 7r1t+l).ndlf
ist eine Funktion f , No3. No definiert.
a)

BestimmenSie f(6,0,1).

b)

BeweisenSie: f(x,y,z) terminierrfür alle r,y,zG No mit x>y.

c)

BeweisenSie, daß flrjr alle r,y,ze B.Iomit x>y gilt: f(x,y,z) ist genau dann eine gerade Zahl, wenn x+ Z ungeradeist.

I