Untitled

Informatik 1

Übungsklausur

Übungsklausur Lösung

Aufgabe 0 (1 Punkt)

Schreiben Sie auf jedes Blatt Name und Matrikelnummer.

Aufgabe 1 (10 Punkte)

a) Entwerfen Sie einen gesteuerten Markov-Algorithmus, der das Produkt zweier natürlicher Zahlen, als Strichfolgen symbolisiert, berechnet.
Beispiel:
Eingabe: | | | * | |
Ergebnis: | | | | | |

b) Führen Sie den Algorithmus für das Beispiel | | | * | | aus. Geben Sie jeweils die Nummer der angewandten Regel an.

Aufgabe 2 (8 Punkte)

Gegeben sei folgende Grammatik G=({S,A,B,C,D}, {a,b,c}, S, P) mit den Projektionen

S -> A
A -> aA | B
B -> bC | D
C -> cC | B
D -> a

a) Von welchem Typ ist die Grammatik?
b) Geben Sie die von G erzeugte Sprache an.
c) Geben Sie einen Akzeptor (deterministischer endl. Automat) an, der G erkennt.

Aufgabe 3 (4 Punkte)

Geben Sie für die folgende Sprache eine kontextfreie Grammatik an.
L = {aⁿb^m w | w Element aus {a,b}^*, |w| = m+n; n,m >0}
Gibt es auch eine reguläre Grammatik, die L erzeugt?

Aufgabe 4 (9 Punkte)

Gegeben sei folgender Boolscher Ausdruck:

a) Wandeln Sie den Ausdruck unter Verwendung der Gesetze der Boolschen Algebra in die konjunktive Minimalform um.
b) Überprüfen Sie das Ergebnis mit einer Wahrheitstabelle.
c) Formen Sie den Ausdruck in Präfix-Notation um.

Aufgabe 5 (4 Punkte)

Gegeben ist folgende Algebra:
Signatur:

create: {} -> alg
Ins: alg element -> alg
Del: alg -> alg
Get: alg -> element

Axiome:

A1: Del(Ins(create,e)) = create
A2: Del(Ins(Ins(a,e1),e2) = Ins(Del(Ins(a,e1)),e2)
A3: Get(Ins(create,e)) = e
A4: Get(Ins(Ins(a,e1),e2)) = Get(Ins(a,e1))

Vereinfachen Sie die folgenden Ausdrücke mit den gegebenen Axiomen. Geben Sie bei jedem Schritt das verwendete Axiom an:

a) Get(Ins(Del(Ins(Ins(create,1),2)),3))
b) Get(Ins(Ins(Del(Ins(create,3)),4),Get(Ins(Ins(create,5),6))))

Aufgabe 6 (4 Punkte)

a) Geben Sie die Bindungen der Variablen in dem gegebenen Ausdruck an.
b) Werten Sie den Ausdruck aus.