GP Based on Chomsky Normal Form
6/31
a1
a2
a3
an
…
A ® a1
B ® a2
C ® a3
S[1, 1]
S[2, 2]
S[3, 3]
S[n, n]
E ® BC
F ® AE
S[1, n]
if S Î S[1, n] then
   S  Þ* a1 … an
Textové pole: …
…
Textové pole: …
…
Idea:
• Input string:
…
S[1, 2]
S[2, 3]
S[n-1, n]
S[1, 3]
…
S[n-2, n]
A Î
B Î
C Î
E Î
F, G Î
D ® AB
D Î
G ® DC