Lecture 9 (CFG Properties), 9/27/17

Concepts, definitions (in italics):

         Grammar G (with start state S) generates a string w iff

o    there is a valid derivation for w in G starting at S

(we will prove it later, when we get our hands on some non-CF languages)



         Do the proofs for Part 1 of above theorem for homework.

         Given a RE, create an equivalent CFG (including homework problem)