Can a PDA with two stacks accept RE Language?

user_11413642 0
Viewed 1816

So, I was having a bit of difficulty figuring what exactly is meant by a String on which Turing Machine does not halt. I read somewhere that a Turing Machine is equivalent to a deterministic automata with 2 stacks. But how will a deterministic automata with 2 stacks accept a string that doesn't halt when for any finite string it is determined to halt... Am I missing something??

pushdown-automaton decidable deterministic formal-languages turing-machines
1 Answers

A PDA with two stacks is equivalent to a Turing machine. To show a TM is at least as powerful as a two-stack PDA, we can use the fact that a TM is exactly as powerful as a two-tape TM. In a two-tape TM, we can restrict usage of the tapes to simulate their being stacks. So, certainly a TM can do whatever a two-stack PDA can do.

To show a PDA with two stacks is at least as powerful as a two-stack TM is a little trickier, but basically the idea is that you can simulate a single tape using the two stacks as follows:

  1. Call one stack L and the other R
  2. The contents of L represent everything to the left of the tape head (including the current symbol)
  3. The contents of R represent everything to the right of the tape head
  4. To overwrite the current symbol: pop from L and push to L
  5. To move left in the tape: pop from L and push to R
  6. To move right in the tape: pop from R and push to L

So, we can move left and right and overwrite symbols. This lets us simulate a tape, which is all a TM can do anyway.

user_8472690
Related