CS 254: Automata and Computability

Assignment #5

Due on paper by 8:30AM Friday, May 13.

A quick assignment to inspire you to think about the CKY algorithm before Sunday night.

Draw the CKY chart and all the parse trees for the string "baaba" and the following grammar:

S → AB | BC
A → BA | a
B → CC | b
C → AB | a