Prütungrtollnobroor

Prlllungrtermln

Etnzelpr{llunglnurupr

Kennzehl:

HERBST

Kennwort:
Arboltrpleta-Nr.

66110

t99l

:

Errte Staetrprilfun3 für etn l.ohramt an öffentltchen Schulen
- Prttlungraufgabsn -

Freh:

Inlormeük (verüeft rtudrert)

Ebrelprilfrrng:

Autmetentheorle,Algorlthm.

fiszrhl dcr 3ertdlten
Anrehl der llmckrelten

sprachen

Themen (Aufgaben):

I

dleter Vorlege:

{

blttc

wendenl

.I itr'
I

P R .T E R H I Nr

Horbst lggl

IXe gotornt Hlflingranfgabe

EINZELPRUFUNGSN
: R6. 6 l l o / s E r r E 2

betteht stt den nachfoeendm Aufgabm t - 1.

Aufgrbc 1
Gegebenseien das Alphabet 4 = (r,b) sowie folgende MengenM,
undM r:
M, = Menge aller Zeichenreihenüber A, die mindestensein
PaaraufcinanderfolgenderZeichenr enthalten,
Mz= Mengealler Zeichenreihen
überA, die höchstens
ein paaraufeinanderfolgendergleicherZeichenenthalten.
a)

GebenSie eine reguläreGrammatikan, die M, ats sprachschatz
hat!

b)

GcbenSie einendeterministischen
endlichen
Automatcn
an, dei genau
die Zeichenreihen von M, akzeptiertt

c)

Geben sie cinen regulärenAusdruckan, der eine M e n g e
L v o n Z e i c h e n r e i h e ni j b e r A
beschreibt,fUr die gilt:
M' o LA''

BeweisenSie lhre Behauptung
!
d)

Beweisenoder widerlegenSie: Es gibt eine MengeN von Zeichenreihen
liber A mit
h{z.,' NAr.

Aulgrbo 2
M seidie Mengealler Zeichcnreihen
w überdem AlphabettO,t) mit derEigenschaft,
daß
w doppeltso viele zeichenI wie zeicheno enthält.
GebcnSie eine Turingmaschine
an, die genaudie Menge lv! akzeptiert!

Adgrbo 3
llhwb:

VerwendenSie zur Beschreibung
a., in dieserAufgabezu enfwickelnden
Algorithmen eine Syntax, wie sie i" höherenProgrammiersprachen
------ rwie pASCAI
' ' se' rL'
v

MODUIA

o.ä. üblich ist.

a

i ( . . : v

'

i i r

' . . ,

:J--';i;i4ir.
',
c"ü"'däd.Llüa;"
,
üb;*::
,i::1
ii::'
'
,,s"
'. :-./-{ :l .t.: ,.:r
V . ' * ä J : : j t , l ' ' it i ' - ,
- :

: .

die Mendä' bbchar_.ä[er Binärbäumeüber-e!h|r Grundmenge
char

-i.1";' i':
'),
'i.or",
emp'ty:- bbchar,
enpty ='
Binärbäum,
isempty:bbchar-r boolean, isempty(ö)= rr,re o ! ist teer,
root: bbchar- char,
root(b)= 'Wurzelvon ö, falls b* cmpty,
leftzbbchar.+bbchar,
left(O)= linker Unterbaum
von ö, falls b+ empty,
right: bbchar-+bbchar,
right(b) = rechterUnterbaumvon ö, fath b+ empty,

(Fär b=cmpty ist roor(b), Ieft(b), right(b)jeweils undefiniert.)
Fortselzung näehste Selte!

P R . T E R M I N Tl f o r b r t 1 9 9 1

r)

- I N Z E t P R I , F U N G S NTR .6 6 I L O/ S E I T E 3

Dcllnlcrcn Sic mlt Hilfc dicrcr Grundopcratloncnrckurslv dic fotgcndcnwcltercn
Operatlonon(wobel dicseDefinltionengcgebcncnfelhruf wclterc g."l3o"t dcfinlcrtc
Opcr!tloncnrbglstlltzt wcrdenkönnen)l
at)

Dügleici: bbchrr x bbchar - booleen,

n'
a2t isrord
:bbc
harr boorean,
:;,,?r1ä"'. l?"'"'L',.?l
I :!:;t$ *1"=
i"

a3)
b)

irruoll: bbchar -r boolean,

istvoll(bl = true *

ö ist vollständig.

Dic Opcration antlralten:bbcharx char .. boolean mit
cnthalten(b,71=
true a x ist als Knotenin ü cnthalten
kann rckursiv wic folgt definiert wcrden:
enthalten(b,xl = lf isenptJ(ü) thcn /alse
rlrr rrrrr=
roor(ä) v enthalten(left(a),r) , enthatten(right(b,xll
endlf

'

Gcben Sie - unter Vcnvendungciner gceigllet gcwählten Datcnstruktu,
keller (frjr
Kcllerspcichcr)- cincn itcrativenAlgorithmus an, der enthalten(ö,r)für gegcbenc
ö
und r berechnet!
c)

Unter der Voraursctzung,
daßD gcordnct (sortlcrt) ist, täßt slch enthaltentiner, rekursiv definiercn.
Gebcn Sie dicsc Definition und eincn cntsprcchenden
itcrativ.n Algorithmw (ohnc
Vcrwcndung eincs Kcllcrs) zur Bcrcchnung an !

d)
.

Binäöäum. seicn nun in liblichcr Wcisc durch Geflcchtc ,calisicrt, in pASCAL_Notetion ctwa:
TYTE bbchar = f bbelem;
bbelem = RECORD
wurzel: char;
lub: bbchar;
tub : bbchar
END:

(r linkcr Unterbaumr)
(. rechtcr Untcrbaumr)

Geben sic Argorithmenzur Rcarisicnrngder opcrationen isempty,root und telt gcmäß
dieser Darstellungan !
c)

Gcbca Sie cincn Algorithmusln, dcr dcn Binärbaum

la'
't' , /

/',\

lc'
,
/
\
'n'

'e'

in der DäEtellung von Teilaufgabed) erzeuSt!
Gebcn Sie dazu zunächstcinen Atgorithmus für dic Operation
cpmpose:char x bbcharx bbchar - bbchar
conposlx,b,br) = Binärbaummit Wurzi r, linkem Unterbaumör und
rechtcmUnterbaumö,
an und vcrwendcn Sie diesenzum Aufbau dcs Binärbaums!
Fortsetzunq nachste Selte!

P R .T E R H I N
s Horbstl99l

EINZELPRUFUNGS
T N6R6.T l o / S E I T E 4

Adgrbc 4
Durchdie Funktlonsvcreinbarung
furrtlqr f(x Jt,z:nat)nat:
lf r =y thcn z rho f(r,yrl,(y*l).d

rndlf

lst eine Funktionft Not-No gegeben.
a)

Bestimmen
Sie denWert von t(4,0,2) !

b)

Beweisensiez f(x,y,z) terminiertftlr alle xy,z€blo mit xry !

,

I

1