Hallo leute ich hätte eine frage, ich muss die aufgaben lösen : (b) Gegeben sei die Grammatik G2 = ({a, b, c, d}, N2, S, P2) mit N2 = {S, A, B, C, D}
und P2 wie unten definiert. Geben Sie eine äquivalente Grammatik G0´2
ohne Zyklen
an.
P2 = {S → ABCS | a,
A → a | aB,
B → C | bA,
C → AD | D | c,
D → B | d}
(c) Gegeben sei die Grammatik G3 = ({a, b, c, d}, N3, S, P3) mit N3 = {S, A, B, C, D}
und P3 wie unten definiert. Geben Sie eine äquivalente Grammatik G0´3
ohne einfache
Regeln an.
P3 = {S → ABCS | a,
A → a | aB,
B → C | bA,
C → AD | D | c,
D → d}
(d) Gegeben sei die Grammatik G4 = ({a, b}, N4, S, P4) mit N4 = {S, A, B} und P4 wie
unten definiert. Geben Sie eine äquivalente Grammatik G0´4
in Chomsky-Normalform
an.
P4 = {S → ABAS | ab,
A → aA | a,
B → b | abb}
Kann mir bitte einer erklären wie man diese grammatik dementsprechend umformen kann ?
Was sind denn die Definitionen der jeweiligen Begriffe?
Ich schätze in G0’2 musst du Kettenregeln entfernen. Dazu ersetzt du einfach deine rechte Seite der Kettenregel durch die möglichen Regeln und machst das so lange bis du keine solche Regeln mehr hast.
Chomsky-NF braucht ein bisschen mehr, aber ich bin ehrlich ich hab noch nichts von „einfachen Regeln“ in dem Zusammenhang gehört.