Prüfungsteilnehmer

Prüfungstermin

Einzelprüfungsnummer

Kennzahl:

Frühjahr
Kennwort:

1999

46TT2

Arbeitsplatz-Nr.:

Erste Staatsprüfungfür ein Lehramt an öffentlichen Schulen
PrüfungsaufgabenFach:

Informatik (nicht vertieft studiert)

Einzelprüfung:

Grundlagender Informatik

Anzahlder gestelltenThemen(Aufgaben): 1
Anzahlder Druckseiten
dieserVorlaee:

3

Biue wendenl

Fdiftjah 1999

46112
Einzelpnifungsnummer:

Seite:2

SämtlicheTeilaufgabensind zu bearbeiten!

TeilaufgabeL:
Gegeben
sei dasAlphabetI : {0,1} und die Sprache
L = { 10i1j0| i undj sind geradeund i, j > 0},
a) Geben Sie einen regulärenAusdruck mit SpracheL an.
b) Konstruieren Sie das Übergangsdiagrammeines nichtdeterministischen,endlichenAutomaten
(ohne Leerübergänge),der (genau)die SpracheL alu,eptiert.
c) Konstruieren Sie das Übergangsdiagrammeines minimalen deterministischenAutomaten, der
(genau)die SpracheL akzeptiert.

Teilaufgabe2z

Ausdrücke:
Gegebenist die folgendeGrammatikzur Erzeugungarithmetischer

9 = ( { E } , { a ,b ,* , * , ( , ) } , P ,E )
mit
P= { E-+E+E IE*E l @) | a Ib} .

a) ZeigenSie, dassdieseGrammatikambig(d.h. nicht eindeutig)ist.
b) GebenSie eineeindeutigeGrammatikmit derselbenSpraehean, so dassdie Ableinrngsbäume
nachder üblichenVorrangregel" * bindetstärkerals * " gebildetwerden.

FortsetzungnächsteSeite!

Frtitrjahr 1999

Einzelpnifungsnuiltmer: 46112

Seite:3

Teilaufgabe 3:
Sei4 : (S,:, ö, s0, 51) ein deterministischer
Automatmit Zustandsmenge
S = {p, q, r, s0, sl}
=
und Aiphabet:
{0,1}. Der Autonat soll durchein Progranmin einerbeliebigenirnperativen
Sprachesimuliert werden.
a) Deklarieren Sie dazu folgendeDatenrypen:
EinenDatentyp"TYPE State= ..." zlr Repräsentation
der Zustandsmenge
S.
"TYPE
ii) Einen unterbereichstyp
Sigma:...' der ganzenzahlet nx Repräsentation
des
Alphabetsl.
iii) EinenDatentyp"TYPE Transition:..." zur Repräsentation
von Zustandsüberg:ngs_
funktionen(d.h. E: S x x + S soll als ein Elementvon "Transition"dargestelltwerden
können).
i)

b) Es sei angenotnmen,dassS1 ausgenaueinemEndzustands1 besteht.SchreibenSie in einer imperativenProgrammiersprache
Ihrer Wahl eiae Prozedurmit Kopf
PROCEDUREekzgplis6(delta:Transition;s0, s1: State);
die elementweiseeine Folge von Ziffem liest und bestimmt,ob die Folge zur sprachevorr. gehört oder nicht. Das Ende der Folge wird durch die Eingabeeinervon 0 oder 1 verschiedenen
Ziffer gekennzeichnet.
c) DerAutomat5 habeden AnfangszustandsQ: p, den Endzustands 1= r und folgendeübergangsfunktionö:
ö(p,0) - r, ö(p, i) = q, ö(q,0) = r, ö(g, 1) = p, ö(r, 0) = q, E(r, 1) = r.

Die Prozedur "akzeptiert" von Teil b) ist in ein Progranrmeinzubetten,so dassdas Prograrnm
eine Folge von Ziffern liest und bestimmt, ob die Fotge zur Sprachedes obigen Automaten gehört oder nicht.