Home Work 6	Due Mar 14, 2007	Points: 40


Second edition text.

1. Prove that (a^n)(b^n)(c^2n) for n>=0, is not a regular language (prove formally, not with an example as we did in the class, look at the online class note).	[5]

2. Over Sigma = {a, b} derive a CFG for each of the following: [15]

2a. Sigma*
2b. 5.1.1. b 
2c. 5.1.1. c

5.1.4. a, b	[10]

5.1.7. a, b	[10]