Převod do Chomského normální formy – příklady
k procvičení
Příklad 1.
Buď dána bezkontextová gramatika G1 = ({S, A, B}, {a, b}, P1, S), kde množina pravidel P1
vypadá takto:
S → bAS | ABa | ab
A → aBbA | b
B → aa | AbABa | a
Převeďte gramatiku G1 do Chomského normální formy.
Příklad 2.
Buď dána bezkontextová gramatika G2 = ({S, X, Y, Z}, {a, b, c}, P2, S), kde množina pravidel
P2 vypadá takto:
S → bac | Y cXa | aZ
X → SaZY | XS
Y → aZY Sc | cca
Z → bcZ
Převeďte gramatiku G2 do Chomského normální formy.
Příklad 3.
Buď dána bezkontextová gramatika G3 = ({S, A, B}, {x, y}, P3, S), kde množina pravidel P3
vypadá takto:
S → ASy | xxx
A → SABB | AxyB | y
B → SxAyB | xSy
Převeďte gramatiku G3 do Chomského normální formy.
1