Aufgabe 1:
Sei L = {xnb3n | n ∈ N}.
a) Zeichnen Sie den Graph eines DPDA M mit L(M ) = L auf.
b) Geben Sie die formale Beschreibung von M an
Aufgabe 2
Sei G = (V, Σ, P, S) mit V = {S, W, X, Y, Z}, Σ = {a, b, c} und
P = { S → XbZc|bcY a,
W → W c|Y ZX|Z,
X → Y a|Y,
Y → c|aY |bZ,
Z → ZZ|W }
gegeben. Leiten Sie eine Grammatik G′ in Chomsky-Normalform mit L(G) = L(G′) her. Geben
Sie alle hierfür notwendigen Zwischenschritte an
