Computer Science 3719 Assignment 8 Winter 2018. Date due: March 15 (in class) I. Consider the following languages over A = {a,b,c): (a) L = {s| num(a, z) = num(b, z) + num(c, z)), (b) L=(sl num(a, z)=max(num(b, z), num(c,z))), where num(a, z) denotes the number of occurrences of a in the string r. In each case, if the language is context-free, show a pushdown automaton which recognizes it, if the language is not context-free, show why it is so 2. The reflection of a language L over an alphabet A is defined as: Show that the class of context-free languages is not closed under reflection, i.e., find a context- free language such that its reflection is non-contex-free. 3. The following language L over A = {a, b): is not context-free. Find an unrestricted (Chomsky type "O") grammar generating it. Hint: First, a string amgn#Abang can be generated (# is a special symbol erased at the end of generation). Then symbols b can be copied one after another to the right end of the string moving the symbol # to the left for each copied symbol b until # reaches symbols a (and i erased)