.

Pr{lluntrtdtarhlor

pr{ltun3rtrrnla

Etnrelpr{ltunjnrurrr

Rennzrhl:
aa

FRUHJAHR

Kcruwort:
Arbcttrphtz-Nr.

66110

r994

:

Ente St rEprllfiurg tür Gür tchrsnt u öffanülchcn gchulcn
Prllfiurtseufgbcn

Fach:

Intorutük

Elnzdprllfunt:

Autmetcnthcor{arAl!:or{ü r.

Anzrhl der gcatelltcn ltcocn

(vcrltctt

rhrdtcrt)

(A'fgrbcn):

Anzrhl dar Dnrc|rscttcn dlcrcr Vorlag:c:

bLtEe

:
13
I

f

{

_

-

r

-

.

Sprechcn
I
g

wenden I

t:

Pr.lle nnl.nr FrühJahr tgga

Elnzelprülungsnr.

r 66ff0

Eelte z

l. Formale Sprachen/Automatcntheorie
(1") GebcnSieeinetconüextfrcie
Grammatikzu der Worümengä

L-(o'ürfi>j>o)
Eg.

(lb) Einc ltontextfreieGrammatik C heißt,reduzierü,wenn jeder
nichüterminaleSymbot von 6 in einer aus dem Startrymbol ableitbarenKettc vorkommü
und aur
jedem nichütcrminalenSymboleine tcrminale Keütc
ableitbar irt. GebenSie cin
Verfabrcn anr dar zu jeder lcontcxtfreienGramrnatitreine äquivalente
reduzierte
Grammatik tiefert.
(I") BeweirenSie, daß die nicbtdeterminirtirchen,
erlcennendeo
cndlichenAutomaüen
nicht mehr könnenalc die defcrministirchen.
(ld) Konrtruieren Sie einendeterminirüirchen,erkennenden
endlichenAutomaten, der
die Worümengeüber dem Alphabet (o, ö) alczepüiert,die aus alten
Wörtern be
rtehü, die jedc der folgendenBedingungenerfüllco:
'
i. Die lÄnge der worter irt d.rch b t.ilbrr.
ii. Dar wort bcginnümit o und endet mit ö.
iii. oac irü kein Teilwort der Vt/ortes.
2. Bcrechenbarkcit/Algorithmirchc
(2") whileProtrunme

sprachen

bertehenaur Anweirunten der F,iorm:

I :. 0;
X :r rucc(y);
. I sr prod(y);
rhire

r l'

y do Forgr-vo.-Arrciauagea
ead;

wobei X und Y beliebigeVariablen, rucc die Nachfolgerfunktionuoa pEd dte
Vorgängerfunlctionbezeichnet.SchreibenSic eiu While-Prograrnm,das die Addition von n und m realiriert.
(2b) Was verstehtman unter einerprimitiv-rekunivm Funktion? Zeigensie, dag mag
j.de primitiv-rekursiveFunktion dürch cin Whit+Prograrnm realisierenkanu, das
stets hält,.

Fortset,zung nächste selt,e t

Pr. Ttrmln r IrOhJ ehr lgga

llnzolpr0tungrnr.

r 66U0

8clEc 3

(2.) Wir ncnneneino reelleZrhl o ndäcrzngnoed.r
c ben*henbar,wcnner eine berechenbrre F\rnltion /(n) gibt, dic für jedcn Parametern die entcn n Stcllender Dezimdentwiclclungvon o liefert. ?'cigeasie,daß dic Quadratwurzeljedcr natürlicben
Zthl nlherungrweire berecbenbarist. (Dic Berechenbarkeiü
dcr arithmctirchcn
'
Grundopcrationen rci bekannt.)
(2d) ?*igen Sic, daß es reelleZahlenttbt, die ndcätnäherungsweircberechenbarrind.
3, Programmiermethodik
(3") Erläutcra Sie dic auf Floyd und Hoare zuräckgehendeVerifikatiousmethode.(to
Ihrer Antworü mäsgcnmindestenrdic Begriffc Zusichcnrng,rchwächsteVorbedingung und Prädilcaltransformation vorkorunco.)
(3b) Betrachtco Sie folgcndesProgrammfrqgmentmit dcr Nachbcdingungc = n!:
a:r0;

b:. 1; c:r0;

IHfLE c
a s r a + b ;
c :r c + 6;
b : r b + c ;
EIID;
Geben Sie die Schlcifcninvariantcao, und bewcisenSic dicse durch Induktion.
Bcweireo Sie sb zweiter dic Nachbedingung. l4las fehlt daun noäh für eine
vollstäo[it" Veriftlcalion?
4. Übenctzerbau
(a") Wclchesrind dic drei wichüigstenTeilaufgabcu,die ein Codeteneratorin jedem
FalI zu löscn hat? (Hinweia: Dic Optimierung gehört nicht dazu.) Bcröreibeo
Sic dicrc fir,ftaben.
(4b) Gcneriocn Sic Maschinencodezu den bciden folgendcnC-Anweisungen:
r r a/(b+c) - dr(o+f);

atil tjl r btil thl . cftI tjl;
GehcnSicdabci voneiuerZielrnaschinc
mit drei universellverwendbareo
nßgi.
rteru !lt!.
(a.) Erläutern Sic die folgeodenParameteräbergabemechanigmen:
Call-by-value,Call'
by-referense,Call-by-naule uad Copy-Rcstore.
({d) Bcim Aufruf einer Prozcdur mu8 eine Umgebungsbeschreibuog
angelegt werden
(activation rord).

Wclche Informaüionmuß dicse Beschreibungbei pascalähn.ll

liöco Sprachco cnthaltea? Inwiefern vereinfachüsie rich bci Sprrchen. dic keinc
gcschacbtet
tco P rozcdurdeklarationenzulassen?

I
I

't 1

-

.