MT4512 Automata, Langugages and Complexity Class Test
Let G1be the context free grammar (S, {0, 1}, S → 0S |S1 | 0 | 1, S).
(a) For each of the following two words, either give a derivation or prove that it is not in L(G1): 021, 10. [2 marks]
(b) Describe L(G1) and fully justify your answer. [3 marks]
(c) Construct a PDA P s.t. L(P) = L(G1). [2 marks]
3.
Let L1= {(ab)ncnan: n ≥ 0}. Prove that L1 is not context free. [3 marks]
Let L2 be the language{0a1b#0a+b : a, b ∈Z≥0}
over the alphabet {0, 1, #}. Give an implementation-level description of a Turing machine M to recognise L2. [4 marks]
5.
Let M1and M2 be Turing machines, and let L3= L(M1) and L4 = L(M2).
(a) Prove that L3 ∪ L4 is Turing recognisable. [2 marks]
(b) If both M1 and M2 are deciders, is L3 ∩ L4 decidable? Justify your answer. [2 marks]