3.9 Let a k-PDA be a pushdown automaton that has k stacks. Thus a 0-PDA is an NFA and 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.
Solution: Clearly, 2 PDA can do any thing which 1-PDA can. Now I will give a language which is accepted by 2-PDA not 1-PDA. { w |w ∈ anbncn } is one I want to consider. This is not A CFL and so not accepted by a 1-PDA. But if there are 2 stacks then do as follow:
Read input a*b*c*
1. Initially PDA is in state qaccept. If an 'a' is read then push it in stack 1 and go to q1. Else if read a 'b' or 'c', go to qreject and stay there for rest of input.
2.Being in state q1 and reading input 'a', push it inside stack 1. Go to state q2 if a 'b' is read and pop one 'a' from stack 1 and also push a 'b' on stack 2. If a 'c' is read then go to qreject and stay there for rest of input.
3. Being in state q2 and reading input 'b', pop 'a' and push 'b' in stack 2. If a 'c' is read then go to state q3 and pop 'b' from stack 2. If no a is remaining on stack with 'b' still in hand, go to qreject. Reject if 'a' is read again.
4. Being in state q3 and reading input 'c', pop 'b' from stack 2. Reject if 'a' or 'b' is read.
5. Accept if both of the stacks are empty otherwise reject.
b. Show that 3-PDAs are not more powerful than 2-PDAs.
Solution: 3-PDAs can do whatever 2-PDAs can do. With a 2-PDA, I can simulate a Turing Machine so anything solvable can be done by 2-PDAs as well.
1. Put a input tape in stack 2 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 1. And pop from stack 1, push the popped symbol into stack 2. Finally we will get what we require.
2. The symbol at top of stack 2 is the currant symbol, TM is reading.
3. Suppose current symbol to be read is 'a' and TM will write here a 'b' and moves left, then we will pop 'a' from stack 2 and push 'b' into stack and further pop a symbol from stack1 to push it into stack 2.
4. If machine have made a right move then we would have poped 'a' from stack 2 and push 'b' in stack1.
Read input a*b*c*
1. Initially PDA is in state qaccept. If an 'a' is read then push it in stack 1 and go to q1. Else if read a 'b' or 'c', go to qreject and stay there for rest of input.
2.Being in state q1 and reading input 'a', push it inside stack 1. Go to state q2 if a 'b' is read and pop one 'a' from stack 1 and also push a 'b' on stack 2. If a 'c' is read then go to qreject and stay there for rest of input.
3. Being in state q2 and reading input 'b', pop 'a' and push 'b' in stack 2. If a 'c' is read then go to state q3 and pop 'b' from stack 2. If no a is remaining on stack with 'b' still in hand, go to qreject. Reject if 'a' is read again.
4. Being in state q3 and reading input 'c', pop 'b' from stack 2. Reject if 'a' or 'b' is read.
5. Accept if both of the stacks are empty otherwise reject.
b. Show that 3-PDAs are not more powerful than 2-PDAs.
Solution: 3-PDAs can do whatever 2-PDAs can do. With a 2-PDA, I can simulate a Turing Machine so anything solvable can be done by 2-PDAs as well.
1. Put a input tape in stack 2 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 1. And pop from stack 1, push the popped symbol into stack 2. Finally we will get what we require.
2. The symbol at top of stack 2 is the currant symbol, TM is reading.
3. Suppose current symbol to be read is 'a' and TM will write here a 'b' and moves left, then we will pop 'a' from stack 2 and push 'b' into stack and further pop a symbol from stack1 to push it into stack 2.
4. If machine have made a right move then we would have poped 'a' from stack 2 and push 'b' in stack1.
yo
ReplyDelete