CFG bez jednoduchých pravidel – příklady k procvičení
Příklad 1.
Buď dána bezkontextová gramatika G1 = ({S, A, B, C}, {a, b}, P1, S), kde množina pravidel P1
vypadá takto:
S → C | aBS
A → Aa | aBbA
B → bbS | A
C → abb | bAC | CaC
Odstraňte jednoduchá pravidla v gramatice G1.
Příklad 2.
Buď dána bezkontextová gramatika G2 = ({S, A, B, C, D, X, Y, Z}, {a, b, c, d}, P2, S), kde množina
pravidel P2 vypadá takto:
S → B | X
A → aB | cd
B → S
C → ZaS | aSa | bc
D → aaa | baC
X → C | Y
Y → D | Y Y aa
Z → ZZZ | dc
Odstraňte jednoduchá pravidla v gramatice G2.
Příklad 3.
Buď dána bezkontextová gramatika G3 = ({S, W, X, Y, Z}, {a, b, c}, P3, S), kde množina pravidel
P3 vypadá takto:
S → abba | W
W → Y ca | ac
X → Z | W
Y → S | cac | aZ
Z → W | bZa
Odstraňte jednoduchá pravidla v gramatice G3.
1