IB102 – úkol 11, příklad 2 – řešení Odevzdání: 10. 12. 2012
Vypracoval: James Bond UČO: 007
Skupina: MI6
1. [2 bod] Rozhodněte pomocí CYK algoritmu, zda gramatika G generuje slovo daabb
(daabb ∈ L(G)).
G = ({S, A, B, C, D}, {a, b, c, d}, P, S)
P = { S → AA,
A → CD | a | AA,
B → SS | b,
C → DA,
D → AB | d }
Řešení:
D
A −
C D −
C S, A D −
D A A B B
d a a b b
Slovo daabb lze generovat jedině z neterminálu D a tedy daabb /∈ L(G).