// grammar from page 83
// G = ( V, T, P, S )      V = { A, S )    T = { a, b }  S = S


start S
terminal a b ;

S -> a A S ;
S -> a ;
A -> S b A ;
A -> S S ;
A -> b a ;

enddef
a
abaa
aaaa
aaaaaaa
aabbaa
abab
Productions in P matrix
0. S a   A   S   ; 
1. S a   ; 
2. A S   b   A   ; 
3. A S   S   ; 
4. A b   a   ; 
Productions in P matrix after first pass Chomsky
0. S Z   A   S   ; 
1. S Y   ; 
2. A S   X   A   ; 
3. A S   S   ; 
4. A W   V   ; 
5. Z a 
6. Y a 
7. X b 
8. W b 
9. V a 
Productions in P matrix after Chomsky
0. S Z P 
1. S Y O 
2. A S J 
3. A S G 
4. A W D 
5. Z a 
6. Y a 
7. X b 
8. W b 
9. V a 
10. U   ; 
11. T S U 
12. R   T 
13. Q A R 
14. P   Q 
15. O   ; 
16. N   ; 
17. M A N 
18. L   M 
19. K X L 
20. J   K 
21. I   ; 
22. H S I 
23. G   H 
24. F   ; 
25. E V F 
26. D   E 
set up P1 and P2 for CYK
Type in an input string
string read |!|
finished cyk_main