3

A k-PDA is a pushdown automata with k stacks. My textbook on Computation Theory has an exercise that asks to prove that 3-PDA is no more powerful than a 2-PDA.

Now consider the language that I made up while trying to think of a counter-example:

$ L = { (a|b)^{m}(c|d)^{m}e^{n} }$

where $n$ = no. of positions in which the symbol in the "a|b" substring corresponds to the "c|d" substring. Here "corresponds" means that the $i^{th}$ symbol in the "a|b" substring is $a$ and $i^{th}$ symbol in the "c|d" substring is $c$. (Likewise for $b$ and $d$.)

To recognise this language with a 3-PDA, use the following state machine:

  1. Read the input symbol. If symbol is $a$ or $b$, push it to stack#1. Keep looping in state 1.
    • On an $<\epsilon,\epsilon, \epsilon>$ transition, move to state 2. (non-determinism)
  2. Read an input symbol. If symbol is $c$ or $d$, push it to stack#2. Keep looping in state 2.
    • On an $<\epsilon,\epsilon, \epsilon>$ transition, move to state 3. (non-determinism)
  3. Without reading any input, pop one element from stack#1 and stack#2. If these are $(a,c)$ or $(b,d)$, then push a $X$ to stack#3. Keep looping in state 3.
    • If either stack#1 or stack#2 becomes empty while the other still has symbols, then reject.
    • If not, then when both stacks become empty, on an $<\epsilon,\epsilon, \epsilon>$ transition, move to state 4. (non-determinism)
  4. Read an input symbol. For every $e$, pop one $X$ from stack#3. Keep looping in state 4.
    • If you run out of $X$'s on the stack while input still remains, or vice-versa, then reject, else accept.

I cannot figure out how this could be recognised with a 2-PDA, without the 3rd stack for a "backing store" to keep track of the number of matches, but the book says that a 3-PDA is no more powerful than a 2-PDA, meaning a 2-PDA should recognise any language than a 3-PDA can.

Any ideas on how I should proceed with this? PS: Drawing the PDA transition diagrams here is cumbersome, so I have tried describing the diagram with the above description. Let me know if something is not clear.

Masked Man
  • 233

2 Answers2

4

Two stacks can emulate a Turing machine tape. Motion along the tape is isomorphic to popping some symbol $x$ from one stack and pushing it onto the other stack. Writing to the tape is isomorphic to popping something from one stack and writing the new thing to that stack. Thus, anything a one tape Turing machine can do, a 2-PDA can do. Since a Turing machine can simulate a $k$-PDA for finite $k$, it can certainly simulate a 3-PDA. Therefore a 2-PDA is just as computationally powerful as a 3-PDA.

Eric Towers
  • 67,037
0

I think the following outline implements a $2$-PDA for the language:

  1. First push some marking symbol $\mathtt{\#}$ onto both stack one and stack two.
  2. When you read $\mathtt{a}$ or $\mathtt{b}$ push the corresponding symbol onto stack one.
  3. When you first read either a $\mathtt{c}$ or $\mathtt{d}$ pop all the non-marking symbols from stack one and push them onto stack two.
    • At the same time, if you just read a $\mathtt{c}$ and the last non-marking symbol pushed was an $\mathtt{a}$, push, say, $\mathtt{a}$ onto stack one; similarly if you just read a $\mathtt{d}$ and the last non-marking symbol pushed from stack one was a $\mathtt{b}$.
  4. As you continue to read $\mathtt{c}$s and $\mathtt{d}$s from the string, check to see whether the top symbol of stack two is an $\mathtt{a}$ or a $\mathtt{b}$, respectively, and push something onto stack one accordingly.
  5. Once an $\mathtt{e}$ is read, start counting them against the symbols pushed onto stack one.
  6. Whenever something goes wrong, reject the string.

The point is that in step 3 we're putting all the symbols into the correct order to be compared against the next set of expected symbols from the tape. At the same time we're emptying stack one, so it can be put to a new use.

user642796
  • 52,188