40
$\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?

$\endgroup$

migrated from cstheory.stackexchange.com Jul 20 '12 at 7:06

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\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 Jul 19 '12 at 12:08
  • $\begingroup$ @TysonWilliams: yes, so? $\endgroup$ – Lazer Jul 19 '12 at 17:01
  • $\begingroup$ This is confusing. I don't know what subset of the two claims you want justification for. $\endgroup$ – Tyson Williams Jul 20 '12 at 14:34
  • $\begingroup$ For the one in bold, as mentioned in the question. $\endgroup$ – Lazer Jul 20 '12 at 15:45
  • 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 Jul 20 '12 at 15:58
38
$\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.

$\endgroup$

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.