Bonusblatt

Düsseldorf, 27.06.2016
Übung zur Vorlesung
Informatik IV
Bonusblatt 1, Abgabe: 04.07.2016 bis 16:00 Uhr
Besprechung: 13.07.2016 bis 18.07.2016
Markieren Sie bitte deutlich bis zu 5 Aufgaben, die korrigiert werden sollen. In jeder
markierten Aufgabe können jeweils maximal 10 Punkte erreicht werden.
Bonusaufgabe 1:
Geben Sie eine kontextfreie Grammatik für folgende Sprache an:
L = {ai bj ck | i, j, k ≥ 1 ∧ (i = 2j ∨ 3j = k)} ⊆ {a, b, c}∗
Bonusaufgabe 2:
Gegeben sei der DFA M = (Σ, Z, δ, z0 , F ) mit Σ = {0, 1}, Z = {z0 , z1 , z2 , z3 , z4 , z5 , z6 , z7 },
F = {z5 } und δ wie folgt:
δ
0
1
z0
z2
z5
z1
z6
z3
z2
z4
z5
z3
z1
z6
z4
z3
z1
z5
z7
z7
z6
z3
z1
z7
z7
z7
Konstruieren Sie den zu M äquivalenten Minimalautomaten M 0 mit der Methode aus der
Vorlesung. Geben Sie M 0 dabei formal an.
Bonusaufgabe 3:
Ein NFA M = (Σ, {z0 , z1 , z2 }, δ, {z0 , z1 }, {z2 }) sei gegeben durch Σ = {a, b}, Z = {z0 , z1 , z2 }
und die Überführungsfunktion δ :
δ
a
b
z0
{z0 , z1 }
{z0 }
1
z1
{z2 }
∅
z2
∅
∅
Bestimmen Sie nach der Potenzmengenkonstruktion von Rabin und Scott den DFA M 0 mit
L(M 0 ) = L(M ).
Bonusaufgabe 4:
Zeigen Sie mit dem Satz von Myhill und Nerode, dass die Sprache
L = {an cb3n | n ≥ 1}
nicht regulär ist.
Bonusaufgabe 5:
Gegeben sei die Sprache
L = {an bm cn·m | n, m ≥ 0}
Zeigen Sie mit Hilfe des Pumpinglemmas, dass L nicht kontextfrei ist.
Bonusaufgabe 6:
Gegeben sei G = ({a, b}, {S, A, B, C, D, E, F, G, X}, S, R) mit
R = {S → AC | AD | AB | BE | BA,
A → a,
B → b,
C → SA,
D → GB,
E → GA,
F → GX,
G → XX | XF | a | b,
X → a | b}.
Prüfen Sie mit dem CYK-Algorithmus, ob das Wort w = baba in L(G) liegt.
Bonusaufgabe 7:
(a) Zeigen Sie anhand von Abschlusseigenschaften regulärer Sprachen, dass
L1 = {0k 1m 2n | k, m, n ≥ 4}
regulär ist.
2
(b) Zeigen Sie anhand von Abschlusseigenschaften regulärer Sprachen, dass
L2 = {0k 1n | 0 ≤ k < n}
nicht regulär ist.
Bonusaufgabe 8:
Betrachten Sie die Funktion f : N → N mit
f (n) =
(
n−2
falls n ≥ 2
undeniert sonst.
Zeigen Sie durch Angabe einer geeigneten Turing-Maschine M , dass die Funktion f Turingberechenbar ist. Dabei ist eine gültige Eingabe und Ausgabe immer eine eindeutige Binärdarstellung der Eingabe- bzw. Ausgabezahl ohne führende Nullen. Denken Sie unbedingt
an die Beschreibung der Zustände.
Bonusaufgabe 9:
Gegeben sei die folgende rekursiv denierte Funktion h : N → N.
h(0) = 1, h(1) = 1, h(2) = 1 und
h(n) = h(n − 1) + h(n − 2) + h(n − 3) für n ≥ 3
Zeigen Sie, dass h primitiv rekursiv ist.
Hinweis: Nutzen Sie aus der Vorlesung bekannte Äquivalenzen unter den Berechnungsmodellen aus.
3

Download Report