Aufgabe herunterladen

Sprachen und Automaten Anmerkungen
 grundlegendesAnforderungsniveau
 Vorbereitungszeit:30min
Aufgabe
ComputermüssenfürdieAbarbeitungvonBefehleninderLageseinzuerkennen,obdieseBefehlekor‐
rektgeschriebenwurdenodernicht.DiemathematischeBeschreibungeinersolchenerkennendenEin‐
richtungistdasModelldesEndlichenAutomatenA=(X,Z,,z0,ZE),zudemauchdieAkzeptorengehö‐
ren.
1a NennenSiedreiweitereBeispielefürdieVerwendungvonAkzeptoren.
1b GebenSiedieBedeutungderElementeX,Z,,z0undZEinderDefinitiondesAkzeptorsan.
1c BeschreibenSiedenAufbaueinesGerätes,mitdemdieArbeitsweiseeinesAkzeptors
veranschaulichtwerdenkann.
2. GegebenseifolgenderAkzeptorA=(X,Z,,z0,ZE)mitZE={z0,z2}unddertabellarischen
DarstellungderFunktion:

z0
z1
z2
z3
a
z1
z3
z1
z3
b
z0
z2
z3
z3
c
z0
z3
z0
z3
a) GebenSiedieElementederMengenXundZan.
b) ZeichnenSieeinenZustandsgraphenfürA.
c) GebenSiean,obdiefolgendenWörtervomAkzeptorAerkanntwerden,undbegründenSieIhre
Entscheidung:w1=abc,w2=bca,w3=cab.
d) GebenSieallevomAkzeptorAerkanntenWörtermitgenauzweiZeichenan.
e) BestimmenSiedievomAkzeptorAerkannteSpracheL(A).
3. DiskutierenSiedieAussage:
„ZujederdenkbarenformalenSprachelässtsicheinAkzeptorkonstruieren.“
1
Erwartungshorizont
Aufg.
erwarteteLeistungen
1a
PIN‐Prüfer,Prüfbitgenerator,Parser,…
1b
X…Eingabealphabet(nichtleere,endlicheMenge)
Z…Zustandsmenge(nichtleere,endlicheMenge)
…Überführungsfunktion
z0…Startzustand
ZE…MengederEndzustände(nichtleere,endlicheMenge,TeilmengevonZ)
1c
EssindverschiedeneErwartungsbilder– jenachAbstraktionsebenedenkbar.
AbstrakteGerätebeschreibungmitEingabeband,Lesekopf,ZentraleinheitundSignallampe.
AlternativeBeschreibungenaufkonkretererEbene(realerAutomat)istebenfallsmöglich.
2a
X={a,b,c},Z={z0,z1,z2,z3}
2b
2c
w1L(A),daVerarbeitungdesWortesimEndzustandz0endet.
w2L(A),daVerarbeitungdesWortesimZustandz1endetunddieserkeinEndzustandist.
w3L(A),daVerarbeitungdesWortesimEndzustandz2endet.
2d
{bb,bc,cb,cc,ca}
2e
L(A)istdieSpracheallerWörterüberX,dieentwederauskeinemabestehen
(einschließlichdemleerenWort)oderbeidenennachjedemagenaueinbkommt.
3
DieseAussageistfalsch.EsgibtSprachen,z.B.L={anbn|nN},dienichtvoneinem
Akzeptorerkanntwerdenkann,dadiesernurendlichvieleZuständehabenkann.Zur
ErkennungderangegebenenSprachewärenaberunendlichvieleZuständeerforderlich,
umsichdieAnzahldesZeichenazumerken.
2
ZuordnungzudenProzess‐,Inhalts‐undAnforderungsbereichen
Aufg.
Prozessbereiche
MI
BB
SV
KK
Bewertungseinheiten in
Anforderungsbereichen
Inhaltsbereiche
DI
ID
AL
SA
IS
X
IMG
I
II
III
2
1a
X
X
1b
X
X
2
1c
X
X
3
1
2a
X
X
2
X
3
X
3
X
1
1
2b
2c
X
X
X
X
2d
X
X
2e
X
X
X
2
X
X
2
7
10
5
3
X
X
Summe22
3

Download Report