4. A 2-stack PDA is similar to an ordinary PDA, but has two stacks. Thus, any tr

Question

4. A 2-stack PDA is similar to an ordinary PDA, but has two stacks. Thus, any transition for a 2-stack PDA has the form (q,x,Z1,Z2) = (p,X1,X2), meaning that in state q, looking at input symbol x with Z1 on top of stack 1, and Z2 on top of stack 2, the machine passes to state p, pops Zi and pushes Xi on stack i, where Xi is some stack symbol (or , of course).
Show that 2-stack PDAs are more powerful than ordinary PDAs by describing (informally, but clearly) a 2-stack PDA that recognizes the non-CFL {w!w | w {0,1}}.

Explanation / Answer

The 2-stack PDA is more power full than 1-stack PDA because 2-stack PDA can simulate as 1-stack PDA just by removing the second stack. Let L = {w!w | w {0, 1} } which is not context-free recognize by 2-stack PDA but not by 1-stack PDA.

Consider string S = 0^n 1 ! 0^n 1 L. Let first string = 0^n 1 and second string = 0^n 1. Push initial symbol on each stack which mark ad bottom of the stacks. Then for each first string input, push input onto both stacks till encounter the middle string. For each second string input scanned, pop input from first stack there should be corresponding symbol on the stacks. Finally if there is no input on stacks, then accept.

Since it keep track of the string S to ensure that first string and second string match. Thus 2-stack PDA recognizes the every language as 1-stack PDA and also recognizes which are not by 1-stack PDA. So, 2-stack PDA are more powerful than ordinary PDAs.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.