Question

Let a k - PDA be a pushdown automaton that has k stacks. Thus a 0 - PDA is an NFA and a 1 - PDA is a conventional PDA. You already know that 1 - PDAs are more powerful (recognize a larger class of languages) than 0 - PDAs.

a. Show that 2 - PDAs are more powerful than 1 - PDAs.

b. Show that 3 - PDAs are not more powerful than2 - PDAs. (Hint: Simulate a Turing machine tape with two stacks.

Short answer

a). Two- push down automata are more powerful than one- push down automata is proved.

b). Three- push down automata are not more powerful than two-push down automata is proved.

Step-by-step solution

Step 1: Deterministic context free grammar.

NOTHING

Two- push down automata are more powerful than one- push down automata.

a).

2 PDA can apply where 1-PDA can. Now I will give a language which is accepted by 2 PDA not 1-PDA.

$\left\{\overline{)w}w\in a^n{b}^n{c}^n\right\}$ is one and now consider that this is not a context free language and so not accepted by a 1 PDAs. But if there are two stacks then do as follow:

Read input a* b* c*

1. Initially push down automata is in state q_accept If an 'a' is read then push it in stack one and go to state one.

Else if read a 'b' or 'c', go to q_reject and stay there for rest of input.

2.Being in state state one and reading input 'a', push it inside stack one. Go to state state two if a 'b' is read and pop one 'a' from stack one and also push a 'b' on stack two. If a 'c' is read then go to q_reject and stay there for rest of input.

3. Being in state two and reading input 'b', pop 'a' and push 'b' in stack two. If a 'c' is read then go to state three and pop 'b' from stack two. If no 'a' is remaining on stack with 'b' still in hand, go to q_reject. Reject if 'a' is read again.

4. Being in state three and reading input 'c', pop 'b' from stack two. Reject if, 'a' or 'b' is read.

5. Accept if both of the stacks are empty otherwise reject.

Two- push down automata are more powerful than one- push down automata hence proved.

Three- push down automata are not more powerful than two-push down automata.

b).

Three-PDAs can do whatever 2 PDAs can do. With a 2 PDA, and simulate a Turing Machine so anything solvable can be done by 2 PDAs as well.

1. Put a input tape in stack two such that its left end is on top. Well if some one objects that input is read from left and so left most will be at bottom of stack, then I will suggest to put whole string in stack one. And pop from stack one, push the popped symbol into stack Finally, we will get what we require.

2. The symbol at top of stack two is the present symbol, Turing machine is reading.

3. Suppose current symbol to be read is 'a' and Turing machine will write here a 'b' and moves left, then we will pop 'a' from stack two and push 'b' into stack and further pop a symbol from stack one to push it into stack two.

4. If machine have made a right move then we would have popped 'a' from stack two and push 'b' in stack one.

Three- push down automaton are not more powerful than two-push down automata is proved.