prüfungster:uin

Prüfuagsteirnehner

Eiazelprüfungsnumer

Kennzahl:

Frühjahr

66110

Kenawort:

r996

Arbeitsplatz-Nr

Erste

.:

Staatsprüfuug

für

ein

Lehrant

aD öffentlichen

' Prüfungsaufgaben

Fach:

f nformatik

Eiuzelprüfhng

:

Anzahl

der

gestellten

Anzahl

der

Druckseiten

(vertieft

Automatentheorie

Vorlage:

Bitte

studiert

, Algorithn.

Themen (Aufgaben):
dieser

-

wenden !

1
z

)

sprachen

Schulea

.Erunl anr

19 9 6

stimtliche

Einzelprüfungsnr.

3 66110

Seite:

2

Teilauf gaben sind zu bearbeiten !
:

1) ZeigenSie, daßes zu jedem(nichtdeterministischen)
endlichenerkennenden
Automaten
Aspmit spontanen
(nichtdet.) end0bergängen
einenäquivaienten
lichen erkennenden
gibt!
Automaten
Anspofinespontani0bergänge
(Hinweis:8ei einemspontanen
(z,e,z,) wird kein Symbol
Obergang
eingeiesen.;
2) Konstruieren
Sie einen linear beschränkten
Automaten,
der die Sprache
L = {u5v lu ist Prefix von v} akzeptiertl
3) ZeigenSie, daßes zu jeder nichtleeren,rekursivaufzählbaren
Menge
A
natürlicher Zahleneine primitiv rekursiveFunktionf gibt, derenüildmeirge
A ist!
4) Für we'lche.SprachenKlassender Chomsky-Hi
erarchi e ist das Wortprobl
ementscheidbar (Begründung
| )?
5 ) E r k l ä r e nu n dv e r g i e i c h eSn i e d i e A u f r u f p r i n z i p i e ,nc a i l b y v a l u e ' u n d
'ca| | Dy reference':
6) Geben
Sie eine Syntax-Graphen-Darste
I 1ungzur EBNF
"
(
"
8
"
)
'
.
A="x" I
B=AC. C={,,+',A}.

i