problem 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).
problem 2: (Language to PDA) Design a PDA whose language is {a^{m}b^{n}c^{p}d^{q} | m + n = p + q}.
problem 3:
(a) (Language to CFG, closure property) Construct CFG for the following language L = {b^{i} a^{2i }| 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
problem 4: (Pumping lemma) Use pumping lemma to show that the following language is not context free {0^{i}1^{j} | i is not a multiple of j}
problem 5: Show that the language L = {a^{i}b^{j} |i ≠ j) is context free.