Insert Format Tools Table Window Help Document Layout References Mailings Review View Tell me Aa A 21 Aa Bbce de AaBbCcDdEe No Space AaBbcc Heading 1 Normal [12 points) This question develops your ability to design CFGs. For each of the following languages, give a CFG. Assume the alphabet is = {0,1). Justify your answers briefly. (a) f* | * is a palindrome). Recall a palindrome is a string that looks the same forwards and backwards. Examples of palindromes are "madam" and "racecar". (b) {* the length of x is odd). (c) (d) {x | does not contain any maximal substring of Is of odd length). For example, 6.011. 111100011 are in the language, but 10011 is not [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) Convent G (from problem #1 above) into a CFG in Chomsky Normal Form. So each rule has the form: ABC or A. (b) Show that if G is a CFG in Chomsky Normal Form, then for any string w E L(G) of length n 1. exactly 2n - 1 steps are required for any derivation of w. En el V ER A w