Homework Assignment 9 Solution



  • Read the CKY Algorithm notes in the resources folder.

  • Use the CKY algorithm to check if the the strings BABAAB and BABABB are in the language given in the example.

  • Give the Turing machine transition table for a TM that accepts the language:

{X {0, 1} | X begins with 0 and has as many 1 to 0 transitions as 0 to 1 transitions}.

Homework Policies: You may study together in small groups and discuss ideas about the homework problems before composing the solutions. You are expected, however, to write the solutions yourselves and not copy them from other students or share your solutions with other students. If you have worked closely with other students on particular problems, then you must mention the names of the people you have worked with and also the problems on which you worked together.


error: Content is protected !!