Question 6 (2007)
i) (be careful of my answer, haven't tested it)
1)Read a,
2)Push X onto stack
1
3)Repeat 1 - 2 till b is read
5)Read b
6)Read b
7)Pop X from stack
1 push X onto stack
2
8)Repeat 6 - 7 till Pop /\ from stack
1
9) Pop X, then Pop X from stack
2
10)Read a
11)Pop X from stack
2
12)Repeat 10 - 11 till Pop /\ from stack
2
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.