cykp v0.9 starting adding production q0 -> 0 q3 adding production q0 -> 1 q1 adding production q1 -> 0 q1 adding production q1 -> 1 q2 adding production q1 -> 1 adding production q2 -> 0 q2 adding production q2 -> 1 q2 adding production q2 -> 0 adding production q2 -> 1 adding production q3 -> 0 q4 adding production q3 -> 1 q3 adding production q3 -> 0 adding production q4 -> 0 q4 adding production q4 -> 1 q4 adding production q4 -> 0 adding production q4 -> 1 reading input finished. Start symbol: q0 Variables: q0 q1 q2 q3 q4 Terminals: 0 1 Sorted productions: q0 -> 0 q3 q0 -> 1 q1 q1 -> 0 q1 q1 -> 1 q2 q1 -> 1 q2 -> 0 q2 q2 -> 0 q2 -> 1 q2 q2 -> 1 q3 -> 0 q4 q3 -> 0 q3 -> 1 q3 q4 -> 0 q4 q4 -> 0 q4 -> 1 q4 q4 -> 1 Eliminate epslion Productions Eliminate Unit Productions after eliminate, sorted productions: q0 -> 0 q3 q0 -> 1 q1 q1 -> 0 q1 q1 -> 1 q2 q1 -> 1 q2 -> 0 q2 q2 -> 0 q2 -> 1 q2 q2 -> 1 q3 -> 0 q4 q3 -> 0 q3 -> 1 q3 q4 -> 0 q4 q4 -> 0 q4 -> 1 q4 q4 -> 1 after eliminate, Variables: q0 q1 q2 q3 q4 Chomsky 1, replace terminal with variable Chomsky part 1, sorted productions: T_0 -> 0 T_1 -> 1 q0 -> T_0 q3 q0 -> T_1 q1 q1 -> 1 q1 -> T_0 q1 q1 -> T_1 q2 q2 -> 0 q2 -> 1 q2 -> T_0 q2 q2 -> T_1 q2 q3 -> 0 q3 -> T_0 q4 q3 -> T_1 q3 q4 -> 0 q4 -> 1 q4 -> T_0 q4 q4 -> T_1 q4 Chomsky Part 2 generated productions after Chomsky, sorted productions: T_0 -> 0 T_1 -> 1 q0 -> T_0 q3 q0 -> T_1 q1 q1 -> 1 q1 -> T_0 q1 q1 -> T_1 q2 q2 -> 0 q2 -> 1 q2 -> T_0 q2 q2 -> T_1 q2 q3 -> 0 q3 -> T_0 q4 q3 -> T_1 q3 q4 -> 0 q4 -> 1 q4 -> T_0 q4 q4 -> T_1 q4 after Chomsky, Variables: T_0 T_1 q0 q1 q2 q3 q4 about to parse 0110 run CYK algorithm to build array, size=4 Finished first row of VV table VV(1,1)= T_0 q2 q3 q4 VV(2,1)= T_1 q1 q2 q4 VV(3,1)= T_1 q1 q2 q4 VV(4,1)= T_0 q2 q3 q4 Finished 2 row of VV table VV(1,2)= q1 q2 q3 q4 VV(2,2)= q0 q1 q2 q4 VV(3,2)= q1 q2 q3 q4 VV(4,2)= Finished 3 row of VV table VV(1,3)= q1 q2 q3 q4 VV(2,3)= q0 q1 q2 q3 q4 VV(3,3)= VV(4,3)= Finished 4 row of VV table VV(1,4)= q0 q1 q2 q3 q4 VV(2,4)= VV(3,4)= VV(4,4)= 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 10100111 run CYK algorithm to build array, size=8 Finished first row of VV table VV(1,1)= T_1 q1 q2 q4 VV(2,1)= T_0 q2 q3 q4 VV(3,1)= T_1 q1 q2 q4 VV(4,1)= T_0 q2 q3 q4 VV(5,1)= T_0 q2 q3 q4 VV(6,1)= T_1 q1 q2 q4 VV(7,1)= T_1 q1 q2 q4 VV(8,1)= T_1 q1 q2 q4 Finished 2 row of VV table VV(1,2)= q1 q2 q3 q4 VV(2,2)= q1 q2 q3 q4 VV(3,2)= q1 q2 q3 q4 VV(4,2)= q0 q2 q3 q4 VV(5,2)= q1 q2 q3 q4 VV(6,2)= q0 q1 q2 q4 VV(7,2)= q0 q1 q2 q4 VV(8,2)= Finished 3 row of VV table VV(1,3)= q0 q1 q2 q3 q4 VV(2,3)= q0 q1 q2 q3 q4 VV(3,3)= q1 q2 q3 q4 VV(4,3)= q0 q1 q2 q3 q4 VV(5,3)= q1 q2 q3 q4 VV(6,3)= q0 q1 q2 q4 VV(7,3)= VV(8,3)= Finished 4 row of VV table VV(1,4)= q0 q1 q2 q3 q4 VV(2,4)= q0 q1 q2 q3 q4 VV(3,4)= q0 q1 q2 q3 q4 VV(4,4)= q0 q1 q2 q3 q4 VV(5,4)= q1 q2 q3 q4 VV(6,4)= VV(7,4)= VV(8,4)= Finished 5 row of VV table VV(1,5)= q0 q1 q2 q3 q4 VV(2,5)= q0 q1 q2 q3 q4 VV(3,5)= q0 q1 q2 q3 q4 VV(4,5)= q0 q1 q2 q3 q4 VV(5,5)= VV(6,5)= VV(7,5)= VV(8,5)= Finished 6 row of VV table VV(1,6)= q0 q1 q2 q3 q4 VV(2,6)= q0 q1 q2 q3 q4 VV(3,6)= q0 q1 q2 q3 q4 VV(4,6)= VV(5,6)= VV(6,6)= VV(7,6)= VV(8,6)= Finished 7 row of VV table VV(1,7)= q0 q1 q2 q3 q4 VV(2,7)= q0 q1 q2 q3 q4 VV(3,7)= VV(4,7)= VV(5,7)= VV(6,7)= VV(7,7)= VV(8,7)= Finished 8 row of VV table VV(1,8)= q0 q1 q2 q3 q4 VV(2,8)= VV(3,8)= VV(4,8)= VV(5,8)= VV(6,8)= VV(7,8)= VV(8,8)= 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 0111 run CYK algorithm to build array, size=4 Finished first row of VV table VV(1,1)= T_0 q2 q3 q4 VV(2,1)= T_1 q1 q2 q4 VV(3,1)= T_1 q1 q2 q4 VV(4,1)= T_1 q1 q2 q4 Finished 2 row of VV table VV(1,2)= q1 q2 q3 q4 VV(2,2)= q0 q1 q2 q4 VV(3,2)= q0 q1 q2 q4 VV(4,2)= Finished 3 row of VV table VV(1,3)= q1 q2 q3 q4 VV(2,3)= q0 q1 q2 q4 VV(3,3)= VV(4,3)= Finished 4 row of VV table VV(1,4)= q1 q2 q3 q4 VV(2,4)= VV(3,4)= VV(4,4)= 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 1000 run CYK algorithm to build array, size=4 Finished first row of VV table VV(1,1)= T_1 q1 q2 q4 VV(2,1)= T_0 q2 q3 q4 VV(3,1)= T_0 q2 q3 q4 VV(4,1)= T_0 q2 q3 q4 Finished 2 row of VV table VV(1,2)= q1 q2 q3 q4 VV(2,2)= q0 q2 q3 q4 VV(3,2)= q0 q2 q3 q4 VV(4,2)= Finished 3 row of VV table VV(1,3)= q1 q2 q3 q4 VV(2,3)= q0 q2 q3 q4 VV(3,3)= VV(4,3)= Finished 4 row of VV table VV(1,4)= q1 q2 q3 q4 VV(2,4)= VV(3,4)= VV(4,4)= finish CYK algorithm, check for S in VV[1][n]and thus Accepted string rejected by G, string is not in L(G)