Prüfungsteilnehmer Prüfungstermin Einz rüfungsnummer

Kennzahl:

Herbst
Kennwort: 461 13
1998

Arbeitsplatz-Nr.:

Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen

- Prüfungsaufgaben -
Fach: Informatik (nicht vertieft studiert)
Einzelprtifung: Theoretische Informatik

Anzahl der gestellten Themen (Aufgaben): 2

Anzahl der Druckseiten dieser Vorlage: 3

Bitte wenden!
Herbst 1998 Einzelprüfungsnummer: 46113 Seite: 2

Thema Nr. 1
Sämtliche Teilaufgaben sind zu bearbeiten!
Aufgabe 1:

Gegeben sei die Grammatik G mit {a,b} als Menge der Terminalzeichen, den Variablen S,A,B, der
Startvariablen S und den Produktionen

S>abA,S>bBS>a4A-B,A>aB->aS,B-b.

Sei L die von G erzeugte Sprache.

a. Geben Sie eine zu G äquivalente Typ-3-Grammatik in Normalform an!

b. Konstruieren Sie einen nicht-deterministischen Automaten, der L akzeptiert!
c. Konstruieren Sie einen deterministischen Automaten, der L akzeptiert!

d. Geben Sie einen regulären Ausdruck für L an!

Aufgabe 2:

Sei L = { wI1,(w) = 1,(w) } die Menge aller Wörter über {a,b}, die gleich viele Vorkommen von
a und b haben (1,(w) = Anzahl der Vorkommen von x in w).

a. Zeigen Sie, dass L eine kontextfreie Sprache ist, durch Konstruktion eines Kellerautomaten, der
L akzeptiert oder durch Konstruktion einer L erzeugenden kontextfreien Grammatik!

b. Ist L regulär? (Begründung)
Aufgabe 3:

Sei die (partielle) Funktion f: N’—> N ( N Menge der natürlichen Zahlen einschließlich 0)
gegeben durch f(x,y) = if x > y then f(x - y, y) else if x < y then f(x, y - x) else x

a. Berechnen Sie f(18,12) !

b. Bestimmen Sie den Definitionsbereich Df von f!

c. Zeigen Sie, dass f(x,y) für (x,y) e Df der größte gemeinsame Teiler von x und y ist!

d. Ist f primitiv rekursiv? (Begründung!)

e. Ist f° = <(x,y) > if (x,y) e Df then f(x,y) else O > primitiv rekursiv? (Begründung!)

f. Geben Sie ein GOTO-Programm für f an!(Verwendung von Makros der Form
»X, i = % -"x,“ zur Berechnung der modifizierten Differenz ist erlaubt.)
Herbst 1998 Einzelprüfungsnummer: 46113 Seite: 3

Thema Nr. 2

Sämtliche Teilaufgaben sind zu bearbeiten!
Aufgabe 1:
Ist folgendes Problem entscheidbar? (Begründung!)
* gegeben: Turingmaschine M
- entscheide: M berechnet die Identitätsfunktion < x > x > (auf N)
Aufgabe 2:
Sei F die Formel ((A —> B) a (BC) a (C > A)) > (C > B)
a. Ist F erfüllbar? (Begründung!)
b. Ist F eine Tautologie? (Begründung!)
Aufgabe 3:
Sei F die Formel V z V x 3 y P(f(x, y), Z).
Seien N und Z zwei Strukturen mit den Trägermengen U" = Menge der natürlichen Zahlen (einschließlich 0) bzw. U? = Menge der ganzen Zahlen, PY bzw. P? die jeweilige Identitätsrelation und
f bzw f? die jeweilige Additionsfunktion.
a. Ist N Modell von F? (Begründung!)
b. Ist Z Modell von F? (Begründung!)
c. Ist F erfüllbar? (Begründung!)
d. Ist F allgemeingültig? (Begründung')
e. at F pränexe Normalform? (Begründung!)

f. Geben Sie zu F eine äquivalente pränexe Normalform F’ an!