cykp v0.9 starting adding production S -> A B adding production S -> B C adding production A -> B A adding production A -> a adding production B -> C C adding production B -> b adding production C -> A B adding production C -> a reading input finished. Start symbol: S Variables: A B C S Terminals: a b Sorted productions: A -> B A A -> a B -> C C B -> b C -> A B C -> a S -> A B S -> B C Eliminate epslion Productions Eliminate Unit Productions after eliminate, sorted productions: A -> B A A -> a B -> C C B -> b C -> A B C -> a S -> A B S -> B C after eliminate, Variables: A B C S Chomsky 1, replace terminal with variable Chomsky part 1, sorted productions: A -> B A A -> a B -> C C B -> b C -> A B C -> a S -> A B S -> B C Chomsky Part 2 generated productions after Chomsky, sorted productions: A -> B A A -> a B -> C C B -> b C -> A B C -> a S -> A B S -> B C after Chomsky, Variables: A B C S about to parse baaba run CYK algorithm to build array, size=5 Finished first row of VV table VV(1,1)= B VV(2,1)= A C VV(3,1)= A C VV(4,1)= B VV(5,1)= A C Finished 2 row of VV table VV(1,2)= A S VV(2,2)= B VV(3,2)= C S VV(4,2)= A S VV(5,2)= Finished 3 row of VV table VV(1,3)= VV(2,3)= B VV(3,3)= B VV(4,3)= VV(5,3)= Finished 4 row of VV table VV(1,4)= VV(2,4)= A C S VV(3,4)= VV(4,4)= VV(5,4)= Finished 5 row of VV table VV(1,5)= A C S VV(2,5)= VV(3,5)= VV(4,5)= VV(5,5)= 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 ab run CYK algorithm to build array, size=2 Finished first row of VV table VV(1,1)= A C VV(2,1)= B Finished 2 row of VV table VV(1,2)= C S 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 ba run CYK algorithm to build array, size=2 Finished first row of VV table VV(1,1)= B VV(2,1)= A C Finished 2 row of VV table VV(1,2)= A S 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 bba run CYK algorithm to build array, size=3 Finished first row of VV table VV(1,1)= B VV(2,1)= B VV(3,1)= A C Finished 2 row of VV table VV(1,2)= VV(2,2)= A S VV(3,2)= Finished 3 row of VV table VV(1,3)= A 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) about to parse bb run CYK algorithm to build array, size=2 Finished first row of VV table VV(1,1)= B VV(2,1)= B Finished 2 row of VV table VV(1,2)= VV(2,2)= finish CYK algorithm, check for S in VV[1][n]and thus Accepted string rejected by G, string is not in L(G)