Complete one of the following problems for bonus points. If you complete more than one, only the first will be graded. (a) (Minimal CFGs) Give an example of a context-free language L that, for any CFG with language L, requires at least 2 variables. Prove that there is no CFG for L with only 1 variable.^1 (b) (Symbol-Minimal CFGs) Consider the string a^n for some integer n. The language {a^n} clearly is regular (it has only 1 string), and hence is context-free. A simple CFG for it is S rightarrow a middot middot middot a. We will consider the complexity of a^n to be the following: we sum for every rule the number of variables and terminals in that rule as well as the rightarrow symbol. For example, the complexity of an is at most n + 2 since the grammar above has 1 variable, n occurrences of the symbol a, and one rightarrow symbol. We can improve this in some cases. For a^9, we can make the grammar S rightarrow BBB, B rightarrow aaa, which has 5 variable occurrences, 2 rightarrow occurrences, and 3 terminals, which sums to 10 (better than the trivial bound of 11). For what n can we have a better complexity than n + 2, and what n require n + 2? (This appears to be a research-level problem in general). Write a program to generate the complexity (with a CFG with that complexity) for all n lessthanorequalto 100. Discuss how you designed your program, as well as discuss what you believe the "correct" answer is. For extra bonus points, give some complexities for much larger n (say, at least 10^5)