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

Assume E is context-free and p be the pumping length.

• Consider z = 0^P1^P0^P1^P L.

• Since |z| > p, there are u, v, w, x, y with the end goal that z = uvwxy, |vwx| < p, |vxl|> 0 and uv^iwx^iy L for all I > O.

• max must straddle the midpoint of z.

Assume vwx is just in the primary half. At that point in uv^2wx^2y the second half begins with 1. Subsequently, it isn't of the shape ww.

Situation when max is just in the second half. At that point in uv^2wx^2y the principal half finishes in a 0. Along these lines, it isn't of the frame ww.

Assume max straddles the center. At that point utPwx°y must be of the frame 0^P1^i0^j1^P, where it is possible that I or j isn't p. Thus,uv^0wx^0yE.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

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