Q I Maximum score 15 write a grammar that generates the language L-[xxl x-ta,bn Note if x-x, x, then xs_ x" xi Q.2. Maximum score-35 Consider the context free grammar with the following production rules, with S as the starting state, terminal alphabet (a,b), and non-terminal alphabet (A,S): (a) Give the leftmost derivation of abbaaaaa (5 points) (b) Describe the language generated by the grammar (10 points) ( c) Put the grammar into Chomsky Normal Form. Give all the intermediate steps (20 points). Q. 3 Maximum score-20 Using CYK algorithm determine if the string 00000 can be derived from the following grammar Q.4 Maximum score- 20 (10 points for each part) Draw Deterministic Finite Automata to accept the following sets of strings over the alphabet (0,1): a. All strings that contain exactly 4 "Os. b. All strings ending in "1101" Q.5 Maximum score 10 Give a clear English description of the language accepted by the following DFA