1)Convert the following context free grammar to Chomsky Normal Form S a X | Yb

X S |

Y b Y |

2)Some languages distinguish between uppercase and lowercase in identifiers. What are the pros and cons of this design decision?

3)Use the pumping lemma to prove that the following languages are not regular. (The alphabet is = {a, b}.) a) L = {aⁿ b¹ a^k: k >= n+ l}

b) L = {ww: w *}

c) L= {a^k2} // this is k square

d) L ={uww^rv :u,v,w ⁺, |u| >= |v|}