CSE 3502, Fall 2017
Homework 7: TM Variants
due 11/8/17
in class


Problem 1. Computation trees for Nondeterministic TMs.

The following is a diagram of a part of some NTM computation tree on input abb, starting with the initial configuration; for the transitions (labels on edges), we only show the new character, head move, and new state (in that order).


a) Under each node, write its address (defined as in the proof of theorem 3.16); the address of the root is ɛ.

b) List the addresses for all the nodes from the diagram in breadth-first order.

c) We are traversing the computation tree, and we have reached node 312; what are the transitions that need to be made to reach this node from the root of the tree?  Show them as a list of 5-tuples:

(current state, input char, new char, head move, new state).

d) Inside each node, write the configuration that corresponds to it, in textbook's notation (as we've done for the root).


Problem 2. 2-stack PDAs

We can define a class of 2-stack PDAs (or "2PDA" for short), which have 2 stacks instead of one.  On any transition, 2PDAs can push and/or pop either or both stacks. (This is analogous to how multitape TMs can read/write multiple tapes on each transaction) Just as for regular PDAs, both stacks are initially empty.

(a)   Give a formal definition of 2PDA (including of the transitions).

(b)   What would its configuration consist of? What would be an initial configuration?  A final configuration? Given a current configuration and a transition, how do we compute what the next configuration will be?

Hint: look at the definitions of a 2-tape vs. a 1-tape TM for inspiration.

Problem 3. Simulating 2PDAs with Multitape TMs

Having defined a 2PDA properly (problem 2), we can show that one can simulate any (single-tape) TM M with a 2PDA AM. Given any configuration of M in textbooks notation (for example abaqcda), we will use the left stack to hold the left half of Ms configuration including state (abaq in the example) and the right stack to hold the state and the rest of Ms configuration (cda in the example).

a)      Create a 2-PDA Ainit that takes its input string and then sets up a configuration which would match the initial configuration of M. Let it go to ACCEPT state upon setting up that configuration.

b)      Consider an arbitrary configuration of M with current state q and current character c. The corresponding configuration of AM will have q on top of left stack and c on top of right stack. Let <q,c,d, X, q> be the transition in M that would be made next. Describe in detail what transitions AM will need to make to simulate this transition; consider separately the cases of X = R and X = L.

c)      If M has k states and m transitions, what can you say about the number of states and transitions in AM?

Problem 4.

Above weve shown how to simulate any (single-tape, single-head) TM with a 2PDA.

It is also possible to simulate any 2-PDA with a three-tape TM, where the first tape of MA initially contains the input string and the other two are initially empty.  The contents of the first tape never changes, and the other two correspond to As stacks.


It is also the case that the class of TMs is more expressive than the class of regular (1-stack) PDAs.

Based on the three facts above, what can you conclude about the class of 2PDAs? How does it compare with regular PDAs? How does it compare with Turing Machines?

State your answers as Theorems and prove them.