f

-\
"

l

-aa

I

?nfftnestellaeäac=

mfuagsternla

Eaundahlr

HERBST
1909

tansuorbr

Arbettaplstz-Xr.

Erste

r

St'artgprtfuas
.

tacbl
(_

fEs sll

66n0

lgäeagü ra öffeatucfa

i- kitfurr€Esuf8Bbea

Informatik (vertieft

El:rzalplülEgr

Elazei@c=

-,

studiert)

Automatentheor.ie, Algorithmische Sprachen

fass,hl

dal gratellteq

lhsnca

ftz8hl

dgr ltllileqeLto

dlercr

(eufeBUea) r t
yorlagcr

F

bitte

wenden!

4

golnlo

Prüfungstermin: Herbst 1989

Seite Z

Einzelprüfungsnummer
: 156f1fl'

Sämtliche Teilaufgaben sind zu bearbeiten!
Teilaufqabe

1

Hinreir: verveaden sie zru Beschreibu"gder in dierer Aufgabezu entvickelndenAlgorithmen eine konkretePrograrnmiersprache
vie PASCAL, MODI tA o.ä. oder
einendiesenSprachenverwandten.in einschlägigenVorleslngen oder Btichern
üblicherveisebenutzten'pseudocode..
Gegebensei der Zeicheworrat A= {a,b,c}. M sei die Mcnge aller Zeichenreihen x übcr
A mit der Eisengchaft,d"8 die Anzahl, wie oft das Zeichen a in x vorkommt,
eine gerade Zahl ist.
d

Die Grernmatik f habe A als Menge dg3 tslnrinalzeichen" die Nichtterrninsl2sichcn
G und U, das A:<iom G rmd die Produktionsregeln
G+e
G --+ bG
G+cG
G --+ aU
U --+ bU
U-rcU
U-aG
( E bezeichne die leere Zeichenreihe.)
BeweisenSie, dag nir den Sprachschatzg(tl

von F gilt: .gm = M.

bl

Geben Sie einen endlichen Automaten an, der genau die Zeichenreihen von M akzeptierr.

c)

Geben Sie eine'kontextfreie Grarnmatik F an, nir die ebenfallg .gf-) = fy! gilt, dic
jedoch weniger Produktionsregelnals I hat.

dl

Formulierea Sie in Anlehnrms an f einen rekrrsiven Algorithmus

*T

TESTM( strinss):boolea$

der test€t, ob eine Zeichenreihe s auE M rst oder nicht. Beveisen Sie, da8 der Algorithmus flir alle Einsaben s der Sorte striru lspninis3l.

Hisvci*n**:ä:,"3mfti*fxi#rffi
'ltit:#:l+"äH
Zeichenreihcr = xtxz...rn:
isempty(r) = ttue <rDx=E
uad, falls x*e:
fttstfr,r4...x,.) = rt,
rcst(xrxr...ro) = rz...xrr.

Fortsetzunq nächste Seite !

1 l.r.lfsttt|;lDl-gl.ilt.l,tIo

ItEl'Lr5L

I ZO7

JEILE

3

Ltnzel.prut ungsnummer:oo | |u

Für ne}'Io rei nun M,. die Mengealler Zeichenreihender Lä'ge n aur M. Die Abbildurg
f,:lNo-D',Io
sei defniert als:

Eremente
vonMn'
e)

.

Beweisen
r,"::1 ilä,:
. , - ' -= [ l ,
atn,
-t
[ 3t * h(n-t]

fallsn=0,
sonsr.

Higveir: Es gibt genEu3n zeichenreihen der Länge n über A.
Formulieren $is nnhnnd von e) einen rekursiven Algorithmus zur Berechmng
von
fr(d für gegebenesn €iNo.Neh'nen Sie dabei an, daS Addition, Subtraktion rmd
Multiplikation' nicht jedoch dic Potcnzienrng als arithmetische Gnrndoperatioaen
zur
verftieung stehen !$tirnrnen sie Gn Abhän8i8keit von n) die Arzahl
der Additionen' Subtraktionen uud Multiplikationen, die gemä8 diegem Algorithmgs
bei der
Berechnung von ä(n) dnrchsefrihrt verden

s)

Beweisen Sie, da8 nir n >0 auch gilt:
lL(n)= 3rfr(n-l)-1.
Was bedeutet diege Beziehrmgim Hinblick auf die Komplexität der Berechnung
von
ä gemä8 0 ?

U Für die Entrelursivierung der Berechnung von ä wird durch die Beziehgng aus g)
eine Einbettung von ä in die Abbildung I,hI8 -Z rrit
g(nt,ml = kr h(11)- n
nahegelegt.
Entwickeln Sie zunächst einen rcpetetiv relursiven Algorithmgs
iur Bereehnung
von 8{n,k,ml für gegebenen*,rnelNo nnd daraus einen iterativen
Atgorithmus
arr Bcrecharmg von ä(n) nir gegebcncsnelNo.

L

Teilaufqabe

?

Dic Abbilörngen nullz No-No und .nrcc: lNo-lNo scien definiert dtsch
null(d = 0,
gncc(d = r+1.
Zu einer Abbilün8 /t lNo*No seien fo: INo*lNo und .fl: INo*6Jo definiert ü11'ch

/o(01= 0, /o(x+t) = t(tok)),
1r(0)= l, /r(x+l) = tqrr(x)).
Die Menge F von Abbilüngen hlo-lNo sei induktiv definiert vie folgl:
il
nullund fltcc sind in .F'enthdte;
iil Ist f e.F,so ist auch.fo ,md tl in .F enthalten
üil Sind f,geF, go irt arrch ä mit ä(x)=1fu{x)) in F enthalten
d

l6glimrnen Sie nullo, nullr, ra,ccorrnd sucel (in rekurrionrfreier Darstellung).
Fortsetzunq nächste Seite !

Prüfungstermin: Herbst 1989

- Seite 4 -

Einzelprüfungsnummer:
4641,G
t
I

b)

Beweisen Sie. da8 die Abbildunsen
eins:lNo-lNo,
ad,d2zlNo'lNo,
mult2zlNo-iNo,
pot2:lNo-lNo,

einc(x) = l,
add2kl = 7+x,
mult2lÄ = 2*x,
pot2kl = 2*

in F eathalten sind.
c)

Beweisen Sie: tst feJ", so ist auch die Abbilüng r: INo-lNo mit
, ,
[,
rtxf =
[o

falls 2fkl+2>3,
sonst

in F enthalten.

Zu einer Abbildung h:lNo-hlo sei run dic Abbilüng
Ackermann- Fuuktion') del'rniert ürch:

acko:[.[o-No ('verallgemciaerte

C

acko(0,y)= lr(y),
ack^(x+l,0) = ack^(x,l),
ackn(x+l,y+1) = acko(x, acku(x+l,y)).
Die nnendlicheFolge ho,hyh2,... von AbbildunsenNo-No sei gegebendnrch:
är(y) = aekn(i,yl
dl

nir t = 0,1,2,...

Beveisen Siei Falls h(0) +0 nnd ä(y+t) >hhl fih alle yelNs, so gilt lür alle ieiNonnd
yeiNo:
dl) hr(yl > y,
d2) är(Y+t) > ht$|,
d3) Q.r(y) > frr(y+l),

d4) är.r(y)> hrhl.

e)
0

BeweisenSie: Falls heF, so gilt \ü
für alle f slNo.
Sei lreF. Siad die Abbildnngen h, (fehlo) dnnn prinitiv-rekursiv ? BeeründenSic lhre
Antvort.

ff