Please solve the following. I'm having issues to even begin this. Thank you.

1. (40 points) THEOREM: A language is regular if, and only if, it is recognized by a regular grammar. (a) (20 points) Prove the following LEMMA: If A is a regular language, then there exists some regular grammar G such that L(G) = A. (b) (20 points) Prove the following LEMMA: If A = L(G) is a language recognized by some regular grammar G, then A is a regular language. 2. (60 points) THEOREM: Context-free languages are closed under union, concatenation, and Kleene star (a) (20 points) Prove the following LEMMA: If A and B are both CFLs, then AU B is also a CFL (b) (20 points) Prove the following LEMMA: If A and B are both CFLs, then A o B is also a CFL (c) (20 points) Prove the following LEMMA: If A is a CFL, then AA UAUU A is also a CFL HINT: To prove (2c) via induction it may be useful to first prove A" for n 2 0 is a CFL using induction