2007 Q6

Question 6 (2007)

i) (be careful of my answer, haven't tested it)
1)Read a,
2)Push X onto stack₁
3)Repeat 1 - 2 till b is read
5)Read b
6)Read b
7)Pop X from stack₁ push X onto stack₂
8)Repeat 6 - 7 till Pop /\ from stack₁
9) Pop X, then Pop X from stack₂
10)Read a
11)Pop X from stack₂
12)Repeat 10 - 11 till Pop /\ from stack₂
13)Read /\
14)Accept

ii) Yes. As 2PDA is equivalent in power to a Turing Machine and a TM is equal to an nPDA (3PDA)

iii) Yes. As above a 2PDA is equivalent in power to a TM.

iv) No. As L is non-context free and PDA only accept context free languages.