CS 476
Homework 3


Assigned: April 24, 2001
Due: May 1, 2001

Is it possible to find, for every CFL without empty string, a grammar such that all its productions are either of the form A -> BCD (i.e., a body consisting of three variables), or A -> a (e.i., a body consisting of a single terminal)? Give either a proof or a counter example.