CSE 237, Homework 8: TMs and Simulations

Dina Q Goldin, Spring 2006
due 4/05/06

A Turing Machine simulator is available on the course web site, in the "links" section. Note that it is not exactly the same as what we have seen in class. For example, it has only one halting state H; it also handles moving-left-at-start differently.

Write the specifications for the following 1-tape Turing Machines and run them in our simulator.  To distinguish reject from accept, print Y on the tape when halting to accept, and N when halting to reject. Try to make the specifications as short and easy to read as you can, with good names and comments where possible. Make sure to test with a variety of input strings!

(a) L1 = {aⁱ b^j c^k | i, j >= 0; k = i - j + 2}

(b) L2 = {strings over {0,1} with at least as many 0's as 1's (# 0's >= # 1's)}

Do not turn this in on paper. Please send your specifications to "dqg@cse.uconn.edu", as text attachments; the subject of your email should be "cse237 homework 8-1". Name these attachments [your-last-name]1.txt and [your-last-name]2.txt, respectively.

Note: if we cannot run your TM specifications by cutting-and-pasting them into the simulator, you get no credit!

We can define a class of machines called "2-PDA" which have 2 stacks instead of 1.  On any transition, they can push or pop either or both stacks.

(a) Give a formal definition of 2-PDA (including its 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 TMs

Having defined a 2-PDA properly (problem 2), we can now show that we can simulate any (single-tape, single-head) TM M with a 2-PDA M'. 

(a) Given an initial configuration C₀ for M, what would be the corresponding initial configuration C'₀ for M'? In general, for any configuration C of M, what would be the corresponding configuration C' of M'?  Hint: In a TM configuration wqu, think of w as contents of one stack and u as the contents of another.

(b) Suppose that M has a transition t which takes it from configuration C₁ to configuration C₂.  What kind of transitions should M' have so it goes from the corresponding configuration C'₁ to the corresponding configuration C'₂? Consider all possibilities for t (such as different types of head motion).  Hint: label the elements of t (which is a tuple) with variable names, and use those in your explanation. 

Problem 4. Simulating 2-PDAs

Having defined a 2-PDA properly and shown how to simulate a TM with it (problems 2-3), we can also show that we can simulate any 2-PDA A with a 2-tape TM A'. 

(a) Describe how you would do this, following the order of your description for Problem 3.

(b) What can you conclude about the class of 1-tape TMs and the class of 2-PDAs?  Explain.