t r

Prllfrugrtcllnducr

Prtllungrtcrnln

Elnrdprilluntanruucr

Kennzrhl:

HERBST
1993

Kennwort:
Arbettspletz-Nr. :

661t0

Erste Stsatsprüfiutg: fifr eh Lehrent an öffenttldren Sdrulen
- Pr{lfiurg:saufgaben

ghrdtert)

Fach:

InformeüI

Elnzelprilfiurg:

Autmetentheorle rAlgorlthn . sprachen

(verüdt

Anzahl der g:estdlten Themen (Aufgeben):

I

Anzafü der Drucksdten

3

dleser Vorlage:

blE,t,e wenden !

\

Pr.Tormln: Herbsc f993

gelce 2

Elnzelprütungsnr. 3 66r10

zu bearbe l C,enI

SämcI i che Te t L auf gaben s lnd

Algorithmen eine Programmiersprachewie
tfiswol": VerwendenSie zur Formulierungvon"Pseudocode",
Vorwie cr in einschlägigen
pASCAL,MODULA o.ä. oder einen
lesungenund Büchernüblichenveisebenutzt wird!

Atrgabo1
den Nicht= (a,b) als Menge der Terminalzeichen,
Gegebensei die GrammarikF mit I
g,
terminalzeichenz, A und dem Axiom Z und den Produktionsregeln
Z q a

Z-+aB
Zq At
A'+ab
A -t aBb
A -+ abA
g_rba
a) .BeweisenSie: I ist mehrdeutig'
b)

Beweisen Sie: Für den Sprachschatz .f(f) von I gilt:

S(n = (a(ba)n:ne 0{e}.
hat wie I'
an,die dengleichenSprachschatz
c) GebenSie eine reguldreGrammarik
d)

endlichenAutomatenan, der genaudie ZeichenGebenSie einen deterministischen
reihenvon S(f) akzePtiert!

Afgnbo 2
w e I* bezeichneA(rY) die
in w.

'' F'?.;i:,i"$t
t;,'
an, die für alle

ForE,seEzung n ä e h s c e s e i t e I

i.''

't

P r . T er m l n : H e r b e g l 9 g 3

Etnzelpnllungsnr.

s 66IlO

SetEe 3

Atrgnbc3
Gegebensei eine FunktionG: SIo- No mit 6(x) s x für alle x € D'fo'
Durch die Funktionsvereinbarung
furstlm F(x:nat)nat:
tf rmod2=0 thn C(x) alm F(F(x-l)) cndif
ist eine FunktionF: blo-No definiert
a)

BeweisenSie:
al) F(x) terminiert für alle x € No.
an Fa[s G(x)=rfür alle reNs, so gilt F(F(x))=F(x) flir alle xe0'lo.

b)

Die FunktionF*: No t No'No sei wie folgt definiert:
' -= [ - ,
F * ( x'Y)
[ r*(r(x),y-l)

falls]=o'
sonst.

bl) BeweisenSie: für alle x e No gilt F(x) = Ft(x,l).
für F* an (die sich
b2) Geben Sie eine repeririv rekursive Funktionsvereinbarung
nicht auf F absti,itzt), und ennvickeln Sie daraus durch Entrekursivierungund
Spezialisierung(gemäßTeilaufgabebl) eineniterativen Algorithmuszur Berechnung von F.

Atrgpbca
(in
für die Syntaxdefinition
Gegebenseien folgendeproduktionsregeln Backus-Naur-Form)
*,-,
(
:
1,2,3,4,5,6,7,9,9))
.,8,0,
(über dem Alphabet
von Gle itpunktZahlen
(Gleitpunktzatrl) -r (Vorzeichen)(nichtnegativeZahl>| (nichtnegativeZahl>
(nichmegarivezahl> -+ (Mantisse)(Exponent)
(Mantisse) + (Ziffemfolge) . (Ziffer)( Ziffernfolge)
(Exponent) -+ E(ganze Zatü) | :
( ganzeZahl> -+ (Vorzeichen)( Ziffer ) ( Ziffernfolge) | <Z iff. t X Ziffernfolge)
(Ziffernfolge) '+ (Ziffer)(Ziffernfolge) | :
(Vorzeichen)- *l( Z i f f e r- )+o l r l z l g l + l s l s l z l a l s

\

a) GebenSie Fürdie Gleitpunktzahl
4.538E-2
denSyntaxbaumgemdßdieserDefinitionan!
b)

des rekursiven Abstiegs
Geben Sie einen Syntaxanalyse-Algorithmus nach der Methode
eine Gleit(,,recursive descent,,) an, der feststellt, ob eine vorgelegle Zeichenreihe
punktzatrl gemiiß dieser Definition ist!