CS370 2005-2006 Test 1 Sample Solutions

Q1.

Three missing rows in the table:
00, _, 99, _, R <BR>
01, X, 01, X, R <BR>
98, X, 98, X, R <BR>

Q2.

The TM removes the first a in the word, replaces the first b it finds with an X, and then removes the last a in the word, and
then goes back to the beginning of the word. It keeps doing this for as long as it can. If it finally ends up with a string
of only Xs, it accepts. If it gets a blank initially it accepts too.

Q3.

Three missing rows are:
00, _, 99, _, R <BR>
01, a, 01, a, R <BR>
03, a, 02, X, L <BR>

Q4.

The TM moves from left to right, skipping Xs, and replaces the first a (respectively, b) it finds with X and then continues
moving right, skipping Xs, and replaces the first b (respectively, a) it finds with X. It then returns to the left of the
word and repeats the process. If it encounters a string of only Xs, it accepts. If it gets a blank initially it accepts too.

Q5.

M = "On input (a,b):
1. Compare a with b.
2. If a is larger, accept, else reject."

Q6.

M = "On input <M,w>:
1. Run M on w.
2. If M rejects, accept."