Question 1

Given a CFG G = (V,Σ,R,S) with set of variables V = {S}, where S is the start variable; set of terminals Σ = {0, 1, (, ), n, *, ∅,ε}. ; and rules:

S → S n S|SS|S* |(S)|0|1|∅|ε

Using this G, solve the following questions. (20 marks)

(1) Give a derivation for the string (0 n (10)*1)*. (11 marks)

(2) Give the corresponding parse tree for the string (0 n(10)*1)*. (9 marks)

Question 2

Consider the following CFG G = (V,Σ,R,S), where V = {S,T,X}, Σ = {a,b}, the start variable is S, and the rules R are:

S → aTXb

T → XTS|ε

X → a|b

Convert this G to an equivalent PDA. (20 marks)

Question 3

Use the pumping lemma to prove that the language A = {02n13n0n  | n ≥ 0} is not context free. (20 marks)

Question 4

The Turing machine M below recognizes the language A = {02n |n ≥ 0}.

Give the sequence of configurations when the input string is 000000. (20 marks)

Question 5

Given the language ECFG  = {⟨G⟩  | G is a CFG with L(G) = ∅}, prove that it is decidable (briefly describe the proof idea). (20 marks)