**CSE
3502, Fall 2017
**

due 11/8/17

**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 ** A_{M}**. Given any configuration of M in textbook’s
notation (for example “aba

a)
Create a 2-PDA A_{init}
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 ** A_{M}** 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

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

**Problem 4.**

Above we’ve 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 ** M_{A}** 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

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.