Assignment 5 (Due 12 May at end of class)

General Rules:

a. Please hand in only your own work.
b. Grades discounted 10% per day late.

Tasks

1) For the Grammar: S -> AB | BC
A -> BA | a
B -> CC | b
C -> AB | a
Use the CYK algorithm (draw the chart) to determine if "aaaaa" is a member of the language generated by G.
2) Prove (create a grammar) or disprove (P.L./Ogden proof or hint use a closure property) the claim that the language where every string has the same number of a's b's and c's (n.b. the letters do not need to be in order) is Context Free.
3) Design a TM which recognizes 0^n1^n0^n for n>= 1. (Each word in L has n 0's followed by the same number of ones, followed by the same number of zeros.)
4) Design a TM which computes the function n^2 (n squared).
5)Design a TM which accepts strings which have equal numbers of 0 and 1 (again, not necessarily in order).