SECTION B (Answer ANY TWO questions in this section) QUESTION 2 a) Consider the following context free language L and string s. L = {x|x{a,b}',x = (ab) (bab)m, m EN} s s = ababbabbab (i) Draw the transition diagram of a deterministic Pushdown Automaton (PDA) for L. Explain how the automaton accepts the string s. Note: 8 marks for the deterministic PDA. 5 marks for the explanation of how the automaton accepts the string s. Stop presenting [13 marks) 13 > 0 (ii) Write down a context free grammar that generates L. Give the derivation for the string s. Note: 5 marks for the grammar. 5 marks for the derivation. [10 marks] b) State the B reduction rule of the lambda calculus. Use this rule to simplify the following expressions. [7 marks] (i) (1x.x 6) (ly.+5 y) (ii) (a x. (^ y. * (+ y 3)) x 4) 3 13 > O Stop presenting [TOTAL MARK FOR QUESTION 2: 30 MARKS)