-
Übungsblatt 1 (Besprechung am 28.10.)
-
Übungsblatt 2 (Besprechung am 11.11.)
-
Übungsblatt 3 (Besprechung am 25.11.)
-
Übungsblatt 4 (Besprechung am 9.12., 13:15 Uhr!)
-
Übungsblatt 5 (Besprechung am 16.12.+13.1.)
-
Übungsblatt 6 (Besprechung am 13.1.)
-
Übungsblatt 7 (Besprechung am 20.1.!!)
Nachtrag zu Übung 1:
Aufgabe 1:
Die gesuchte rechtslineare Grammatik ist:
GG -> a UG | b GU
UG -> a GG | b UU
GU -> a UU | b GG
UU -> a GU | b UG | eps
Die Konstruktion eines äquivalenten regulären Ausdrucks geschieht
wie folgt:
-
Die Grammatik wird durch Einsetzen von UG und GU zu
GG -> aa GG | ab UU | ba UU | bb GG
UU -> aa UU | ab GG | ba GG | bb UU | eps
-
RA-Schreibweise mit Ausklammern von GG bzw. UU:
GG = aa GG + ab UU + ba UU + bb GG
= (aa+bb) GG + (ab+ba) UU
UU = aa UU + ab GG + ba GG + bb UU | eps
= (aa+bb) UU + (ab+ba) GG
+ eps
-
Gleichung für GG lösen, Lösung in UU einsetzen:
GG = (aa+bb)*(ab+ba) UU
UU = (aa+bb) UU + (ab+ba)(aa+bb)*(ab+ba) UU + eps
= ((aa+bb) + (ab+ba)(aa+bb)*(ab+ba))
UU + eps
-
Gleichung für UU lösen: ((aa+bb) + (ab+ba)(aa+bb)*(ab+ba))*
Aufgabe 4:
Chomsky-Normalform der Grammatik E -> E + E | E * E | ( E ) | id
-
Die Einführung neuer NTe für die Terminalsymbole führt zu:
P -> +
M -> *
L -> (
R -> )
I -> id
E -> E P E | E M E | L E R | I
-
Nach Einführung von NTen für lange rechte Seiten:
(die Produktionen für P, M, L, R, I bleiben unverändert)
E -> E E' | E E'' | L E''' | I
E' -> P E
E'' -> M E
E''' -> E R
-
Die Eliminierung der Kettenproduktion E -> I ergibt schließlich:
E -> E E' | E E'' | L E''' | I E' | I E''
E' -> P E | P I
E'' -> M E | M I
E''' -> E R | I R
Last modified: Thu Oct 29 09:39:40 MET 1998