GP Based on CNF: Example 5/5
10/10
G = (N, T, P, S), where N = {A, B, C, S}, T = {a, b},
P = {S ® AC, C ® SB, A ® a, B ® b, S ® c}
Question: aacbb Î L(G)?
a
a
c
b
b
S[1, 1]
S[2, 2]
S[3, 3]
S[4, 4]
S[5, 5]
={A}
={A}
={S}
={B}
={B}
S[1, 2]
S[2, 3]
S[3, 4]
S[4, 5]
=Æ
=Æ
={C}
=Æ
S[1, 3]
S[2, 4]
S[3, 5]
=Æ
={S}
= Æ
S ® AC
S[1, 4]
S[2, 5]
=Æ
={C}
S [1, 5]
={S}
S Î S[1, 5]
YES