Prüf ungsteilnebmer

f,gnn2ehI

Prüfungatermin

Elnzelprüf

ungsuuurner

3

Herbst

66L10

Kennwort,:

r996

Arbeiteplat,z -Nr. :

Erst,e

Staatgprüfungi

für

eia

Irehramt 'aD öf f entllcben
-

Prüfungsaufgaben

(vertieft

Facb,:

Info::matik

Biazelpnifung:

Automateatb.eorie,
gest,ellten.

Anzahl

der

Anzrhl

der Dnrckeeitea

Algorlthm.

Themeu (Aufgaben) :
dieger

Vorlage:

Bitte

gtudiert)

wenden!

1
3

Spracbeu

Scbulen

Einzelpritfungfsuir.

L996

Herbet,

Sämtliche

Teilaufgaben

sind

Seit,e:

: 56110

2

zu bearbeitent

1

Aufgabe

G€geb€DSeifolpsdes Pascal-Programm:
Fogta

ParauctcnGtt;

Ytr E3 latcgcr;
Yaa e: aray[l..2J
procrdurc upd^ato( rrl
ütt B: latcgcr;

of iatagcr;
: iatcgcr

);

brSt!
a:- t3
:

1:y:-

tfAl
lf y ;

etttl;

bcgia
a:-t l
a[1] z- 2i
a[2]:-.7;
rrydate(a,a[a] ) ;
eEd.
G€b€u Sie frlr die folgendeu Paraneteräbergabetechnihenjeweils au, welche Werte die Vahaben.
riabler n, o[1] nnd a[2] am Ende der Pro@g
:

(a) call-by-value
(b) caltby-refereuce
(c) call-by-nane

Aufgabe

.2

Gegebeusei eise hrnktion d : Nr x Nr + Nr, die wie folgt dä6nien ist:
d(z,V\ =a.r

( t
,fallsg:Iodery-I
1, fallsein z existiertmit z . ! = x
{ 0
, sorur!
[

(a) BeschreibeuSie inforrnell (Stichrmrtc), welcheRrnktion durcb d dargestellt wird.

:

(b) SchreibenSie eise relursirt hrnktioa, welchedie Rrnktion d berechuet!Die hrnktionen
DfV pivisiou) und MOD (rnodulo) dürfen nicbt rtrqrcndet werden.
(c) Stetlen Sie das zu lhrer Fhnhion gehörendeFhnktional I auf. Geben Sie dabei audt
die Rnktionalität ron I at.
(d) Zeige! Sie, daß d eis Fixpunkt des Rrnktionds e i$, d.h. dall Ilrr Prograrnm eine
loplemeutienrng tnB d ist.

Fortsetzung

nächete

Seite !

Einzelprrifungfsnr

L996

Herbst

Auf gabe

Seit,e : 3

. : 55110

3

prog=Emierer Sie irr Modula odcr Pascaldie folgeudesDatestypen. F\rnktionen und Pro
zedures:
(a) Defnieren Sie rekursiv des T:rp Tree der binäres Bäurne, deren Kuogen gaue Zahlen
estbalteu.
(b) progannieres Sie eine Fhaktiou isja" die eises binären Baura t aus Aufgabe (a)
qnd eise garze T.zhl n als Eiagabepasanetßrnimmg und einen boole'scbeuWen als
des lVert TBttEliefen Senaudann, n,enn n iu t
Ergpbnis üufutt, so da8 is-i"(t,a)
rorlommt.
.
(c) Sclreibes Sie eine reknrsiye Fhnktiou sehrs[3sluag:
scbacbtclung(r:REtli üt, og: REIL; cps:REAL): REAL'
PRIICEDIßE
der Interrallschacb'
die nahenrngsweisedie wurzel einer reellen zahl nacb der Methode
-^hl,
soll, ug und og sind
werdes
berechset
Wunel
plrrng berechnet,d-b. : ist die
deren
die Geoauigkeit'
ist'
€P!
lqt€rtralls,
öe Uuter- U39r.Obergrenzedes geradebetracbtetcn
werden, falls
abgebrocbeu
soll
soll Die Rekursion
.oit der die Wnrzel berechs.t oid*
wird
F\raltion
Die
Intcrralls [,ts...ogl.
f* :rl ( eps. Dabei sei u der Mittclwert des
arfgende[ lnitt€ls sehrs[33trr;g(rr 0'0, r,r cps)'
qrcrden'
Ikr Absolutbetrag lan', mit Eilfe eiser F\rnlstios ABSi(r) berecbnet

Auf gabe

4

C€geb€ssei der detenqisistischeendlicbeAutomat

lv! -' (Q, t, d,go,F)

f = tq.) uod
Q - tgo,grtilz,es,gr),
d(go'o)= gt ,
d(go,ö)= gz ,
6(gr,a) = gr ,
d(gr,ö):ggr
6(gr'c) = (13,

.

Bit E = {o, ö},

d(gz,c)= gr
6(qz,ä)= gs
6(9r'a)= gr
d(gr,ö)= gr
6(ga'ö)= 93

(a) Zeichnes Sie des Autonat€B ds Übergangdiagrann'
(b) Berechnes Sie einen äquinalenten Automaten rnit rnininialer Anzahl rou Zrutänden.
(c) Gebeu Sie deu Spracbscharzdes Autonaten an (ohne Beweis).
(d) lst dieseSpracheT]'P3 (regulär) ? (mit BeSrüsduDS!)'
(e) ZeigeuSie, daß folgendeSpracbe_.6
C ta)' nicbt T)'P3 (regulär) ist:
L - {selp = El=r i für ein n € N,n > 0}

Aufgabe

5

Gegebcssei die T}'P2 Qjrrrrrnatik G = (y'E'RS)

Y = t S , Ä )E
, :t(,)),P=( {-i4,.

nit

.5-+(SÄ,

S-'!ÄS'
S+(SÄS,

A+)

)'

(a) WelcbeSpracbeC(G) erzeu$ 6 ?
pDA (d.b. eiseu nicbtdetcrEiristischen Kellerautomatcu) K an mit
(b)
\ ' G€bes sie eines
ff(K) ist die Sprache,die
ff(K) = E(G) (ohne Korrekrheitsbeweis).hur Erisneruns:
vou K durö leeres Keller ericanntwird'
parsender sprachec(G) ? weicbe ParsmFech'
(c) Ismeferu ist der pDA K geeiguerzur'
nikeu kensen Sie ?