52
$\begingroup$

In this answer it is mentioned

A regular language can be recognized by a finite automaton. A context-free language requires a stack, and a context sensitive language requires two stacks (which is equivalent to saying it requires a full Turing machine).

I wanted to know regarding the truth of the bold part above. Is it in fact true or not? What is a good way to reach at an answer to this?

Improve this question
$\endgroup$
3
  • $\begingroup$ There are two claims in the bolded text but your question title suggests that you are only interested in one of them. $\endgroup$
    – Tyson Williams
    Commented Jul 19, 2012 at 12:08
  • $\begingroup$ This is confusing. I don't know what subset of the two claims you want justification for. $\endgroup$
    – Tyson Williams
    Commented Jul 20, 2012 at 14:34
  • 2
    $\begingroup$ @Lazer: the bold text contains two statements ("CSL requires two stacks", "two stacks are equivalent to TM"). As CSL is a proper subset of RE, only one can be true. $\endgroup$
    – Raphael
    Commented Jul 20, 2012 at 15:58

2 Answers 2

Reset to default
51
$\begingroup$

Two bits to this answer;

Firstly, the class of languages recognised by Turing Machines is not context sensitive, it's recursively enumerable (context sensitive is the class of languages you get from linear bound automata).

The second part, assuming we adjust the question, is that yes, a two-stack PDA is as powerful as a TM. It's mildly simpler to assume that we're using the model of TMs that has a tape that's infinite in one direction only (though both directions is not much harder, and equivalent).

To see the equivalence, just think of the first stack as the contents of the tape to the left of the current position, and the second as the contents to the right. You start off like so:

  • Push the normal "bottom of stack" markers on both stacks.
  • Push the input to the left stack (use non-determinism to "guess" the end of the input).
  • Move everything to the right stack (to keep things in the proper order).

Now you can ignore the input and do everything on the contents of the stacks (which is simulating the tape). You pop to read and push to write (so you can change the "tape" by pushing something different to what you read). Then we can simulate the TM by popping from the right stack and pushing to the left to move right, and vice versa to move left. If we hit the bottom of the left stack we behave accordingly (halt and reject, or stay where you, depending on the model), if we hit the bottom of the right stack, we just push a blank symbol onto the left.

For a full formal proof, see an answer to another question.

The relationship the other way should be even more obvious, i.e. that we can simulate a two-stack PDA with a TM.

Improve this answer
$\endgroup$
0
1
$\begingroup$

In the answer by @LukeMathieson it is proved, that non-deterministic two-stack pushdown automaton is as powerful as Turing Machine. A stronger statement is also true:

Deterministic two-stack pushdown automaton is as powerful as Turing Machine

Proof:

Because it is known that deterministic queue automaton is equivalent to Turing machine all we need is to prove that deterministic two-stack pushdown automaton is equivalent to queue automaton. And we get this from the fact that we can simulate deterministic queue automaton using deterministic two-stack pushdown automaton in the following way:

Put symbol on top of the queue:

1)Put symbol on top of the fist stack

Read symbol from bottom of the queue:

1)Move symbols one-by-one from the first stack to the second stack until we reach the bottom of the first stack

2)Read element from the top of the second stack

3)Move symbols one-by-one from the second stack to the first stack until we reach the bottom of the second stack

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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