CSE 322
Assignment 7
Due Friday, February 16, 1996
Let be a regular grammar which only has production
of the form and .
Consider the NFA where
is a production in and
is a production in .
Carefully prove the behavioral lemma: For all , and ,
if and only if .
Your proof should be brief, but complete.
(Hint: there are two induction proofs, one for each direction in the
if and only if statement.)