2006 Q6

Question 6 (2006)
i)
1) So read all a's, for every a read, push X onto stack 1. If not a is read n < 1 the 2PDA will crash.
2) After all a's are read/ First b is found (n = stack 1), push 3 more X's onto stack 1 (n+3)
3) For each a that is now read, pop an X from stack 1 and push a Y onto stack 2
4) When stack 1 is empty pop 4 Y's from stack 2 ((stack 1) - 3 - 1)
5) Read all your b's, popping a Y from stack 2 till /\ (stack 2 = empty). If you don't read an b or insufficient b's (n-1) the the 2PDA will crash
6) Read /\ from the tape (tape finished). If tape not empty crash.
7) Accept

ii)
Yes. TM = nPDA and nPDA = 2PDA. The above example is accepted by a 2PDA therefore a Turing Machine, therefore a 3PDA (nPDA)

iii)
Yes. 2PDA = nPDA = TM. (This seems a bit short)

iv)
No. As PDA < nPDA = TM. PDA only accept context-free languages, and this is a non-context free language


YES/NO

Agreed on all above.