Prtlfturgrtcllnchmcr

Prtlfrurgctermln

Ehzclprttfungrnunmcr

Kchnzehl:
Kennwort:
Arbeltsplatz-Nr. :

FRUHJAHR
1990

66110

Erste Staatsprilfrrng fttr etn Lehramt an öffentltchen Sehulen
Prüfungsaufgaben

r
,

Faeh:

Informatlk (vertleft studlert)

Elnzelprtifung:

Automatentheorle,Algorlthm. sprachen

Anzahl der gestellten Themen (Aufgaben):

I

Anzahl der Druekselten dleser Vorlage z

!

,'

bitte nenden!

-

t

tormlnt Früblahr 1990

- Soltc 2 -

t 661l0
snurnmcr

f lnralprüf

s ä mIt i c h e r c t l a u f g a b e ns l n d z u b e a r b e i t e n !
Tellaufgabe I
endliche,nichtzylclische
Gegebensei ein endlichesAlphabet Ä und eine ungeordnete,
K e El, worin die n nicbtleereendliche
Liste von K paaren (r, t) für ein vorgegebenes
aus .4" \ {;} und die t natürlicheZahlenaus N seien. In Ä' steht die
Zeichenreihen
von der Ordnung< in
Ordnungzur Verfügung,die zur Unterscheidung
texikographische
werde.Außerdemtelte für alle n in den Paarender Liste: l"l S f
N Eit tr bezeichnet
x €.A' bezeichnet
tr € nl, wobeinit lzl die LängeeinerZeichenreihe
für ein vorgegebenes
wird.
Die Paareder Liste könnenals einfacheKarteikartenin einerTelefondateiaufgefalltwerden mit der Bedeutung:
n g Nanre
t 4 Telefonnurnmer.
Paare(tri,t,) und (ni,t;) in der Liste gilt:
daß für verschiedene
Es wird vorausgesetzt,
n; * n; und t; * ti.
an, mit denen
durchTYp- und ldentitätsvereinbarungen
l. GebenSieDatenstrukturen
die folgendenTeilaufgabenbearbcir,etwerdenkönnen.
2.

'Formulieren einenAlgoritbmus,mit dessenHilfe eineZugriffsstrukturauf die
Sie
zu einemNamenn
Liste aufgebaut,wird. Die Zugriffsstruktursoll es ermöglichen,
mit der Komplexittt O(log K)
ob die Liste einenEintrag ztrn enthältfund
(") zu entscheiden,
t anzugebenTelefonnummer
die zugehörige
(b) gegebenenfalls

r zugrifr in PASCAL, die den unter 2. formulierten
3. SchreibenSie eine Prozedu
Algorithmus realisiert.
Zugriffs'
4. ScbreibenSieeineProzedursucäe,die mit Hilfe der unter3. aufgebauten
struktur zu einemn € A' feststellt,ob die Liste einenEintrag zu n enthält, und
Telefonnummert ausgibt.Die Komplexitätder Prodie zugehörige
gegebenenfalls
zedur suchesoll O(log K) sein.

'
.

r

't

t

F o r t s e t z u n qn ä c h s t e S e i t e !

{

I

Tellaufqabe 2
Gegebensci dasAlphabetA: {o,ö}. Mit t.bzw. 11werdefür ein r e A'die Zeichenallerü bzw. a aus c entsteht.
reiheaus {a}'bzw. tö}'bezeichnet,die durch Streichen
Seiendso z.B. s = oaboöund ! = bbbb,dann ist c. = oootxt = bb,an = € üDd gr = bbbb.
Gegebensei nun die wie folgt definierteTeilmengeM von A':

sCM

t + a 1l " . l S l " , l ,

wobei für ein x E A' mit lrl die Längevon e bezeichnetwhd.
1. ZeigenSie,daß die MengeM C A'nicht regulärist.
2. M ist als Sprachschatzeiner kontextfreienSpracheüber dem terminalenAlphabet
Sie dieseAussagedadurch,dd SieeinenKellerautomaten
.4 darstellbar.Ben'eisen
yon
dem Sie zeigen,daß er genaudie MeugeM akzeptiert.
angebenr
3. Konstruieren Sie eine kontertfreie Granrmatik über dem terminalen Alphabet .r{,
die in .A' genau die'MengeM erueugt,und begrändenSie die einzelnenSchritte
Ihres konstruktiven Vorgehens.

Tel laufqabe 3
Gegebenseienzn'ei ganzeZahlen p und g mit 0 < g < p und eine wie folgt definierte
rekursiveRechenrrorschÄtt
I fär ganzeZahlenz C Zz

IU?-P))
! ( r'r''-=l { z + q

f ü r z> l o o

'
fürz<100

Sie,da8die Rechenvorschrift
Beweisen
/ für alle.ge Z terminiertundsomiteineF\rnktion

f : Z'Z
definiert.

I

i

Hinweis:
BetrachtenSie tfir z 2 t00 die durch /(r) veranlalltenrekursivenAufrufef (r,) r'on / und
zeigenSie,daß für alle d gilt: z; 1 z.

,&

,{
4

'4
il

4