Homework 5
CMPS 130, F08, MW

Posted 11-5-08
Due 11-12-08, beginning of class

1) 6.39 d) Show all your steps

2) 8.1 a)

3) 8.2 Give three examples

4) 8.8 a)

5) Can the following grammar
     S -->  AB | AC | BC
     A -->  AA | AB | a
     B -->  BB | BC | b
     C -->  CC | AC | a
generate the string babaa?
Use the CYK algorithm.

Show your work by giving the table.

How can the table be used to answer the question
whether the string can be generated or not!

How can the algorithm be augmented so that at the end its
easy to retrieve a derivation tree if the word is in the
language?