Q 9. (a) Let P be the following PDA with input alphabet {0, 1} and stack alphabet {0, }.

(i) Show how P processes each of the following input words, indicating whether each word is accepted or rejected. 

101     1011     1010111

(ii) Write down the language of P using set notation.

(iii) Show that the language of P is not regular.

(b) Consider the context-free grammar, G, with terminal symbols T = {〈,〉, :, x, y, z}, non-terminal symbols N = {σ, E}, starting symbol σ, and production rules

(i) Give a leftmost derivation for the word 〈〈x : y〉: y〉 in the grammar G.

(ii) The following PDA is designed to accept the language L(G) generated by G. The input alphabet is Σ = T and the stack alphabet is Γ = N ∪ T ∪ {}.

Show how this PDA accepts the input string 〈〈x : y〉 : y〉.

(iii) Is L(G) a regular language? Justify your answer.