Drawing the parse tree

Question

Question 1: Given the following grammar S → 0A0 | 1B1 | BB; A → C; B → S | A; C → S | ε,

(a) (Derivation) Given a left-most and right-most derivation of a string 01001110

(b) (Parse tree) Draw the parse tree from step (a).

Question 2: (Language to PDA) Design a PDA whose language is {a^mbⁿc^pd^q | m + n = p + q}.

Question 3:

(a) (Language to CFG, closure property) Construct CFG for the following language L = {bⁱ a²ⁱ | i >= 0}

(b) (CFG to PDA) Design a PDA for the above grammar using a transition diagram and specifying the start/accept state(s), start symbol on the stack.

(c) (PDA computation) Show the stack content, state of the PDA in each step given an input string baa

Question 4: (Pumping lemma) Use pumping lemma to show that the following language is not context free {0ⁱ1^j | i is not a multiple of j}

Question 5: Show that the language L = {aⁱb^j |i  ≠ j) is context free.