cykp v1.0 starting adding production A1 -> A2 A3 adding production A2 -> A3 A1 adding production A2 -> b adding production A3 -> A1 A2 adding production A3 -> a reading input finished. Start symbol: A1 Variables: A1 A2 A3 Terminals: a b Sorted productions: A1 -> A2 A3 A2 -> A3 A1 A2 -> b A3 -> A1 A2 A3 -> a Eliminate epslion Productions Eliminate Unit Productions after eliminate, sorted productions: A1 -> A2 A3 A2 -> A3 A1 A2 -> b A3 -> A1 A2 A3 -> a after eliminate, Variables: A1 A2 A3 Chomsky 1, replace terminal with variable Chomsky part 1, sorted productions: A1 -> A2 A3 A2 -> A3 A1 A2 -> b A3 -> A1 A2 A3 -> a Chomsky Part 2 generated productions after Chomsky, sorted productions: A1 -> A2 A3 A2 -> A3 A1 A2 -> b A3 -> A1 A2 A3 -> a after Chomsky, Variables: A1 A2 A3 generating greiback.pda k A[k] B[k] 0 A1 G_A1 1 A2 G_A2 2 A3 G_A3 kk=0, k=0 A[k]=A1 kk=0, k=1 A[k]=A2 kk=0, k=1, j=0 A[j]=A1 kk=0, k=2 A[k]=A3 kk=0, k=2, j=0 A[j]=A1 found 3 A3 -> A1 adding 5 A3 -> A2 A3 A2 deleting 6 A3 -> A1 A2 kk=0, k=2, j=1 A[j]=A2 fix up deletes in P1 productions are now: A3 -> A2 A3 A2 A1 -> A2 A3 A2 -> A3 A1 A2 -> b A3 -> a kk=1, k=0 A[k]=A1 kk=1, k=1 A[k]=A2 kk=1, k=1, j=0 A[j]=A1 kk=1, k=2 A[k]=A3 kk=1, k=2, j=0 A[j]=A1 kk=1, k=2, j=1 A[j]=A2 found 3 A3 -> A2 adding 5 A3 -> A3 A1 A3 A2 adding 5 A3 -> b A3 A2 deleting 6 A3 -> A2 A3 A2 fix up deletes in P1 productions are now: A3 -> A3 A1 A3 A2 A3 -> b A3 A2 A1 -> A2 A3 A2 -> A3 A1 A2 -> b A3 -> a kk=2, k=0 A[k]=A1 kk=2, k=1 A[k]=A2 kk=2, k=1, j=0 A[j]=A1 kk=2, k=2 A[k]=A3 kk=2, k=2, j=0 A[j]=A1 kk=2, k=2, j=1 A[j]=A2 found 7 A3 -> A3 adding 8 G_A3 -> A1 A3 A2 adding 8 G_A3 -> A1 A3 A2 G_A3 deleting 9 A3 -> A3 A1 A3 A2 found 10 A3 -> != adding 11 A3 -> b A3 A2 G_A3 found 10 A3 -> != adding 11 A3 -> a G_A3 fix up deletes in P1 productions are now: G_A3 -> A1 A3 A2 G_A3 -> A1 A3 A2 G_A3 A3 -> b A3 A2 G_A3 A3 -> a G_A3 A3 -> b A3 A2 A1 -> A2 A3 A2 -> A3 A1 A2 -> b A3 -> a Greibach pass 1 complete, sort and delete duplicates A1 -> A2 A3 A2 -> A3 A1 A2 -> b A3 -> a G_A3 A3 -> a A3 -> b A3 A2 G_A3 A3 -> b A3 A2 G_A3 -> A1 A3 A2 G_A3 -> A1 A3 A2 G_A3 Greiback Pass2 kk=2, k=1 A[kk]=A3, A[k]=A2 found sub A2 -> A3 gamma adding substitute A2 -> a G_A3 A1 adding substitute A2 -> a A1 adding substitute A2 -> b A3 A2 G_A3 A1 adding substitute A2 -> b A3 A2 A1 deleting in pass2 A2 -> A3 A1 Greiback Pass2 kk=2, k=0 A[kk]=A3, A[k]=A1 fix up deletes in P1 Pass2 productions are now: A2 -> a G_A3 A1 A2 -> a A1 A2 -> b A3 A2 G_A3 A1 A2 -> b A3 A2 A1 A1 -> A2 A3 A2 -> b A3 -> a G_A3 A3 -> a A3 -> b A3 A2 G_A3 A3 -> b A3 A2 G_A3 -> A1 A3 A2 G_A3 -> A1 A3 A2 G_A3 Greiback Pass2 kk=1, k=0 A[kk]=A2, A[k]=A1 found sub A1 -> A2 gamma adding substitute A1 -> a G_A3 A1 A3 adding substitute A1 -> a A1 A3 adding substitute A1 -> b A3 A2 G_A3 A1 A3 adding substitute A1 -> b A3 A2 A1 A3 adding substitute A1 -> b A3 deleting in pass2 A1 -> A2 A3 fix up deletes in P1 Pass2 productions are now: A1 -> a G_A3 A1 A3 A1 -> a A1 A3 A1 -> b A3 A2 G_A3 A1 A3 A1 -> b A3 A2 A1 A3 A1 -> b A3 A2 -> a G_A3 A1 A2 -> a A1 A2 -> b A3 A2 G_A3 A1 A2 -> b A3 A2 A1 A2 -> b A3 -> a G_A3 A3 -> a A3 -> b A3 A2 G_A3 A3 -> b A3 A2 G_A3 -> A1 A3 A2 G_A3 -> A1 A3 A2 G_A3 Greibach pass 2 complete, sort and delete duplicates A1 -> a A1 A3 A1 -> a G_A3 A1 A3 A1 -> b A3 A2 A1 A3 A1 -> b A3 A2 G_A3 A1 A3 A1 -> b A3 A2 -> a A1 A2 -> a G_A3 A1 A2 -> b A3 A2 A1 A2 -> b A3 A2 G_A3 A1 A2 -> b A3 -> a G_A3 A3 -> a A3 -> b A3 A2 G_A3 A3 -> b A3 A2 G_A3 -> A1 A3 A2 G_A3 -> A1 A3 A2 G_A3 Greibach Pass3, G_* -> A* substitute found sub 3 G_A3 -> A1 gamma adding substitute 3 G_A3 -> a A1 A3 A3 A2 adding substitute 3 G_A3 -> a G_A3 A1 A3 A3 A2 adding substitute 3 G_A3 -> b A3 A2 A1 A3 A3 A2 adding substitute 3 G_A3 -> b A3 A2 G_A3 A1 A3 A3 A2 adding substitute 3 G_A3 -> b A3 A3 A2 deleting in pass3 G_A3 -> A1 A3 A2 found sub 3 G_A3 -> A1 gamma adding substitute 3 G_A3 -> a A1 A3 A3 A2 G_A3 adding substitute 3 G_A3 -> a G_A3 A1 A3 A3 A2 G_A3 adding substitute 3 G_A3 -> b A3 A2 A1 A3 A3 A2 G_A3 adding substitute 3 G_A3 -> b A3 A2 G_A3 A1 A3 A3 A2 G_A3 adding substitute 3 G_A3 -> b A3 A3 A2 G_A3 deleting in pass3 G_A3 -> A1 A3 A2 G_A3 fix up deletes in P1 Greibach pass 3 complete, sort and delete duplicates A1 -> a A1 A3 A1 -> a G_A3 A1 A3 A1 -> b A3 A1 -> b A3 A2 A1 A3 A1 -> b A3 A2 G_A3 A1 A3 A2 -> a A1 A2 -> a G_A3 A1 A2 -> b A2 -> b A3 A2 A1 A2 -> b A3 A2 G_A3 A1 A3 -> a A3 -> a G_A3 A3 -> b A3 A2 A3 -> b A3 A2 G_A3 G_A3 -> a A1 A3 A3 A2 G_A3 G_A3 -> a A1 A3 A3 A2 G_A3 -> a G_A3 A1 A3 A3 A2 G_A3 G_A3 -> a G_A3 A1 A3 A3 A2 G_A3 -> b A3 A2 A1 A3 A3 A2 G_A3 G_A3 -> b A3 A2 A1 A3 A3 A2 G_A3 -> b A3 A2 G_A3 A1 A3 A3 A2 G_A3 G_A3 -> b A3 A2 G_A3 A1 A3 A3 A2 G_A3 -> b A3 A3 A2 G_A3 G_A3 -> b A3 A3 A2 greibach finished about to parse ba run CYK algorithm to build array, size=2 Finished first row of VV table VV(1,1)= A2 VV(2,1)= A3 Finished 2 row of VV table VV(1,2)= A1 VV(2,2)= finish CYK algorithm, check for S in VV[1][n]and thus Accepted string accepted by G, string is in L(G) about to parse ababab run CYK algorithm to build array, size=6 Finished first row of VV table VV(1,1)= A3 VV(2,1)= A2 VV(3,1)= A3 VV(4,1)= A2 VV(5,1)= A3 VV(6,1)= A2 Finished 2 row of VV table VV(1,2)= VV(2,2)= A1 VV(3,2)= VV(4,2)= A1 VV(5,2)= VV(6,2)= Finished 3 row of VV table VV(1,3)= A2 VV(2,3)= A3 VV(3,3)= A2 VV(4,3)= A3 VV(5,3)= VV(6,3)= Finished 4 row of VV table VV(1,4)= VV(2,4)= VV(3,4)= VV(4,4)= VV(5,4)= VV(6,4)= Finished 5 row of VV table VV(1,5)= VV(2,5)= VV(3,5)= VV(4,5)= VV(5,5)= VV(6,5)= Finished 6 row of VV table VV(1,6)= A1 VV(2,6)= VV(3,6)= VV(4,6)= VV(5,6)= VV(6,6)= finish CYK algorithm, check for S in VV[1][n]and thus Accepted string accepted by G, string is in L(G) about to parse aaa run CYK algorithm to build array, size=3 Finished first row of VV table VV(1,1)= A3 VV(2,1)= A3 VV(3,1)= A3 Finished 2 row of VV table VV(1,2)= VV(2,2)= VV(3,2)= Finished 3 row of VV table VV(1,3)= VV(2,3)= VV(3,3)= finish CYK algorithm, check for S in VV[1][n]and thus Accepted string rejected by G, string is not in L(G)