Let = {0, 1, #}. Is the following language regular; context-free but not regular; or not context-free? Justify your answer {x#y : x, y {0, 1} and bin(x) + 1 = bin(rev(y))} Problem 5 10 marks For languages A and B over , define the language A B as follows: A B = {w : there exists x B such that wx A} Show that if A is context-free and B is regular, then A B is context-free. Problem 6 50 marks Consider the following grammar for representing simple calculations in Polish notation, given by G = (V, , R, E) where V = {E, M, N, I} = {+, , , 0, 1, 2, x, y} R consists of the rules: E +EE | EE | MN | I M | e N 0 | 1 | 2 I x | y (a) Is G ambiguous? Justify your answer. (6 marks) (b) Give a grammar in Chomsky Normal Form that is equivalent to G. (6 marks) (c) Are the following words in the language generated by G? Justify your answer. (i) + + 1y 20 (4 marks) (ii) +1 xx (4 marks) (iii) 0 210 (4 marks) (d) Give a recursive definition for ParseG, the set of parse trees of words in L(G) (6 marks) (e) For symbols X and Y we define Z[X,Y] = {a + bX + cY + dX2 + eXY + . . . : a, b, c, d,e, . . . Z}. For example, 3 + 2X + 5Y + 10XY Z[X,Y]. Recursively define a function eval : ParseG Z[X,Y] that calculates the value of the expression represented by the given parse tree (under the assumption that eval(x) = X and eval(y) = Y. For example, if T were the parse tree of +11, then eval(T) = 2 because 1 + 1 = 2. Likewise eval(+ x21) = (X 2) + 1 = 2X + 1. (8 marks) Simplification Partial marks can be obtained by defining a function eval : ParseG Z that calculates the expression represented by the given parse tree under the assumption that eval(x) = 5 and eval(y) = 7. So eval(+ x21) = (x 2) + 1 = 15 2(f) Explain how you could modify the CYK algorithm, or provide your own algorithm, to compute eval(w) (if possible) for a word w . (4 marks) (g) Demonstrate how your algorithm computes: (i) eval(+ 2x2x) (4 marks) (ii) eval( 1 + x 2y) (4 marks)