Question 4 please, both a and b

Unless otherwise noted, the alphabet for all questions below is assumed to be = {0,1). 1. [12 points] This question develops a basic understanding of CFGs and parse trees. Consider the grammar G below. A A+BB (1) B + BXCIC (2) (A) 5 (3) For each string below, give a parse tree of a derivation in G. (a) 5 (b) 5 x 5+5 (c) ((5 x 5) + (5 x 5)) 2. [5 points] We saw in class that the sets of both regular and context-free languages are closed under the union, concatenation, and star operations. We also saw that the regular languages are closed under complement. In this question, you will investigate whether context-free languages are closed under intersection. Use the languages A = {amba.com.n>0} and B = {a"b" m, n >0} to show that the class of context-free languages is not closed under intersection. You may use the fact that the language C = {a"b"c" n > D} is not context-free. 3. [12 points] This question develops your ability to design CFGs. For each of the following languages, give a CFG. Assume the alphabet is I = {0.11. Justify your answers briefly. (a) {is a palindrome). Recall a palindrome is a string that looks the same forwards and backwards. Examples of palindromes are "madam" and "racecar". (b) {z the length of x is odd}. (c) 0. (d) { does not contain any maximal substring of is of odd length}. For example, e, 011, 111100011 are in the language, but 10011 is not. 4. [12 points] This question develops your ability to convert a CFG into Chomsky Normal Form and to understand properties that result from that form. (a) Convert G (from problem #1 above) into a CFG in Chomsky Normal Form. So each rule has the form: ABC or A a. (b) Show that if G is a CFG in Chomsky Normal Form, then for any string u EL(G) of length n > 1, exactly 2n - 1 steps are required for any derivation of w. 1