CSE 322 Assignment #9
Spring 2000

Due: Friday, June 2, 2000.

Problems:

1. Run the Cocke-Kasami-Younger algorithm for the input babbaa for the following grammar. (Show the full tableau.)
   S' -> e | aB | bA | SS
   S -> aB | bA | SS
   A -> Sa | a
   B -> Sb | b

2. Lewis and Papadimitriou, Problem 3.6.3, page 157.

3. Let B be the set consisting of all infinite binary sequences. (Note that infinite binary sequences are not strings since any string has finite length). Prove that B is not countable using diagonalization.

4. (Bonus) Let HALF-L={x : there is a y with |y|=|x| and xy is in L}. Show that if L is regular then so is HALF-L.