# How does a two-way pushdown automaton work?

Note that by "two-way pushdown automaton", I mean a pushdown automaton that can move its reading head both ways on the input tape.

I recently had the question of determining the computational power of two-way PDAs in the Chomsky hierarchy. I don't entirely understand two-way PDAs, but I can see how with the ability to read in both directions on the input, it could handle languages of the form $L=\{0^n 1^n 2^n\}$. I can't say that for sure, but it seems that would make it powerful enough to least handle context-sensitive languages.

This is all a guess because I don't know exactly how they work. Can someone explain the process of how a two-way PDA operates, maybe even on my example?

UPDATE:

The model is a generalization of a pushdown automaton in that two-way motion is allowed on the input tape which is assumed to have endmarkers.

• "I mean a Push Down automata that can move it's reading head two ways on one stack." Are you sure about that? If something has a reading head (i.e. allows you to access elements other than the one which has most recently been added), it's usually not referred to as a stack anymore. (Plus that's not what the term "2-way PDA" usually means.) – sepp2k Mar 23 '12 at 15:56
• I agree, I'm just repeating what was on my homework last week. I imagine he means take the way a PDA works and give it the possibility of reading both ways. call its datastructure what you will at that point – justausr Mar 23 '12 at 15:58
• I think the meaning is that the stack is still a stack, but the input is given on a read-only tape, and the head of this tape is not restricted. – Ran G. Mar 23 '12 at 15:59
• @RanG. it looks like you're right. I found a paper on this sciencedirect.com/science/article/pii/S0019995867903695 I still don't understand how that would work though since input is given sequentially from what I've experienced. – justausr Mar 23 '12 at 16:09
• @RanG Actually I don't think what's described here would be a Turing machine. If all you change is replacing the stack of the PDA with a tape, the result will be strictly less powerful than a TM because the input still needs to be read one-character per transition. – sepp2k Mar 23 '12 at 16:19

A two-way PDA can accept the canonical context-sensitive language $\{0^{n}1^{n}2^{n} | n \geq 1\}$. Such an automaton could work by checking whether the largest prefix of the form $0^{i}1^{j}$ had $i = j$, using the stack, after which it could empty the stack, and check whether the largest suffix of the form $1^{j}2^{k}$ had $j=k$, again using the stack. So $CFL \subsetneq L(2PDA)$.
The machine would crash if the input string weren't a string of 0s, followed by 1s, followed by 2s; and it would have crashed if the longest prefix of 0s and 1s weren't in the canonical CFL $\{0^{n}1^{n}\}$; and it would have crashed if the longest suffix of 1s and 2s weren't in the canonical CFL $\{1^{n}2^{n}\}$. In this case, the ability to rewind the tape allows you to accept languages which are the intersection of CFLs, by essentially stringing PDAs together, and rewinding the tape in between.
• Is $\mathcal{L}(2\mathrm{PDA})\subseteq \mathrm{CSL}$? – Raphael Mar 23 '12 at 22:04