4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "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.) $\endgroup$ – sepp2k Mar 23 '12 at 15:56
  • $\begingroup$ 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 $\endgroup$ – justausr Mar 23 '12 at 15:58
  • $\begingroup$ 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. $\endgroup$ – Ran G. Mar 23 '12 at 15:59
  • 2
    $\begingroup$ @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. $\endgroup$ – justausr Mar 23 '12 at 16:09
  • 1
    $\begingroup$ @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. $\endgroup$ – sepp2k Mar 23 '12 at 16:19
7
$\begingroup$

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)$.

In more detail, the 2-way PDA would read from left to right as many 0 symbols as it finds, pushing a 0 onto the stack for each 0 it reads on the input tape. If it reads any 0 symbols and finds a 2 symbol before finding a 1, it crashes. When it gets to a 1, it changes state, and begins reading all the 1 symbols, until it comes to a 2. If it reads a 0 symbol while doing this, it crashes. It pops a 0 symbol from the stack for each 1 it reads on the input tape. If, when it reaches the first 2, the stack is empty, the PDA moves the tape head to the end of the input tape. Otherwise, it crashes. If it encounters any 0s or 1s, it crashes. It then reads the input tape left to right, pushing a 2 for each 2 it reads on the input tape. When it gets to a 1, it switches states and begins reading 1s and popping 2s. If, when it gets to a 0, the stack is empty, the string is accepted.

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.

Therefore, the languages accepted by two-way PDAs are trivially closed under intersection, a property not shared by languages accepted by regular PDAs.

$\endgroup$
  • $\begingroup$ Is $\mathcal{L}(2\mathrm{PDA})\subseteq \mathrm{CSL}$? $\endgroup$ – Raphael Mar 23 '12 at 22:04
  • 2
    $\begingroup$ @Raphael the paper in the 5th comment of the question shows how to convert a 2way-PDA into a deterministic LBA. Thus the answer to your question is yes. $\endgroup$ – Ran G. Mar 23 '12 at 23:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.