1. (12 points) Consider the following context-free grammar G and answer the following questions. S A1B A 0A | B B1 | (a) What are the variables, terminals, and the start variable of G? (b) For each of the following, answer True or False i. S 00011 ii. S=> 10101 (c) For the string 00111, give both the leftmost derivation and the parse tree. (d) What language does this grammar generate? 2. (12 points) Consider the following grammar SaS aSbS This grammar is ambiguous. Show in particular that the string aab has two: (a) Leftmost derivations. (b) Parse trees. 3. (12 points) Design CFGs for the following languages. (a) {amn | n 0,m 1}. (b) {w | w * and w=w, where w is the reverse of w}. Here = {a,b}. For example, abba, bab, and baab are all in the language, but bbaa is not. Note that e is also in the language. (c) {abek |i=jor i = k, where i, j, k 0}.