Prüfungsteilnehmer

hüfungstermin

Einzelprüfungsnunmer

Kennzahl:

Frühjahr
Kennwort:

2002

66LL2

Arbeitsplatz-Nr.:

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

Informatik (vertieft studiert)

Einzelprüfung:

AutomatentheorierKomplexität,Algorith.

Anzahlder gestelltenThemen(Aufgaben): 2
Anzatrlder DruckseitendieserVorlaee:

5

Biue wenden!

Frühjahr 2002

Einzelprüfungsnumm
er: 66L12

Seite:2

Thema Nr. L

Sämtliche Teilaufgaben sind zu bearbeiten!

Thema: Automaten,formale Sprachen,rekursiveFunktionen
l. Sei) : {a, b, c } ein Alphabet.Man gebean,von welchemChomsky-T1pi ( mit 1<i<3) die folgandenSprachensind, wobei i jeweils maximal sein soll. Zur Begründunggebemanjeweils eine
Automatenfür die Spracheanund beweise,dass
erzeugendeGrammatikoder einenakzeptierenden
die Sprachedavonerzeugtbzw. akzeptiertwird!

(i)

I.:1akb'cn l0 <k,m,n) sowie
L'=)+-L

(ii)

1=1akb'cnl0 < mck,0 < n)

(iit

L=(>* - {a'b*cn l0 < m,n}) fl a*b*c*

Fortsetzung
nächsteSeite!

Frähjahr 2002

Einzelprüfungsnumm
er: 66I 12

Seite:3

2. WelcheSprachewird von folgenderChomsky-Grammatik
vom Tlp I erzeug!?
S +SAl1$1
1A+All
$A-0S11$1

Hinweis: Offensichtlich werden Wörter der Gestaltu$v erzeugl.Man gebe an, wie die Teilwörter v aussehenund in welcher Beziehungj eweils dasu zvrrrv steht- nafrirlich j eweils mit Beweis!

3. Welche der folgendenFälle desPostschenKorrespondenzproblemshaben eine Lösung,
welche nicht? Man gebeentwedereine Lösung oder eine Begrtindungflir die Nichtlösbarkeit
an!

(i)

(aa, aab),(bb, ba), (abb,b)

(ii)

(aaa, aa),(aaaa,aaa)

(iii)

(a, aaa), (abaaa,ab), (ab, b)

(iv)

(ab, aba),(ba, aa),(abab,baa).

4. Man gebe explizite Darstellungen der folgenden über den ganzenZahlen rekursiv definierten
Funktionen an:

f(x): if x <4 then f(f( x +2)) elsex - 1 end
(x):

if x > 4 then ((x-2)) elsex - 1 end

Hinweis: Man mache eine Fallunterscheidungfür verschiedeneWertebereiche für x und beweise
die einzelnenTeilaussagenmit vollstlindiger Induktion !

-4Frühjahr 2A02

Einzelprüfungsnuulmer
: 66LLz

Seite:4

Thema Nr. 2
SämtlicheTeilaufgabensind zu bearbeiten!
1. SeiL die SpracheallerWörterüberdemZeichenvorrat{a,b}, die doppeltsovieleVorkommenvon
'a'wie von 'b' enthalten.BeweisenSieoderwiderlegen
Sie:

a) L ist kontextsensitiv.
b) L ist kontextfrei.
c) L ist regulär.
-

2. KonstruierenSie einenvolistäindigendeterministischenerkermenden
Automaten,der genaudie
durchdenregul2iren
Ausdruckab*l(ac)*gegebene
SpracheüberdemZeichenvorrat{a,b,c}akzeptiert!

3. ZergenSie die Aquivalenzder beidenregulärenAusdrücke
. bl a(ba)*bb
. (ab)+b
4. BeweisenSie:Ist f: N2-+ N primitiv rekursiv,so ist auchg : N -+ N mit

s @ ) :i f Q , n )
pnmltrv reKursrv.
5. ZeigenSie,dassdie Präfixrelation(präfix(u,v): <--> -3 w € {a,b}* : u w: v) auf {4b}* enr
scheidbarist.
6. Seienpaarcod: N2 -+ N i gr, q:: N -+ N gegebeneprimitiv rekursiveFunktionenmit paarcod(x,y)
: 71--) qr(z): x rnd q2(z): y für alle x, y, z.

a) ZeigenSie,dassdie durch(x€ N, y€ N*, e leereFolge)
. c : N* -> N, c(e)= 0, c((x) o y) = paarcod(x,c(y))
+I
gegebeneFunllion c bijektiv ist.
FortsetzungnächsteSeite!

Frühjahr 2002

Einzelprüfungsnunrmer
: 66LI2

Seite:5

b) Frir Zahlenfolgen(y1,...,yr.)und Zahlenx seiendie Keller-Operationen
Push,Top, Rest,Leer
charakterisiertdurch:
. Push(x,(y1,...,
Vu))= (*, yr,...,yr)

' Top((v',.'.,vr.))
: v'
. Rest((y1,...,
v*)): (v,,..,vu)
. Leer((y1,...,yr)) : ift = 0 thentrueelsefalse

BeschreibenSie primitiv rekursiveFunl:tionenpush,top, rest, leer, die entsprechende
Operationen
auf denCodewertenc(y) von Zahlenfolgeny ausfthren.

7. Aussagenlogik
a) BeweisenSie:"(A + B) + (-S -+-A)" ist eineTautologie.
b) Folgtaus {(A + B), -A} die Formel-B?
c) Formalisieren
Sieaussagenlogisch
die folgendenbeidenAussagenund zeigenSieihre Aquivalenz:
. "Wenn dasKind durstig oderhungrig ist und wir denKoch erreichen,so rufen wir ihn."
. "WermdasKind durstig ist, so rufen wir denKoch, fa1lswir ihn erreichen,und, wenn wir den
Koch erreichen,so rufen wir ibn, wenn dasKind hungrig ist."