1. Trace the execution chains of the following input strings on this machine:

a. aaa

b. aba

c. baaba

d. ababb

2. The language accepted by this TM is all words with an odd number of letters that have a as the middle letter. Show that this is true by explaining the algorithm the machine uses and the meaning of each state. Pay attention to the two necessary parts that must always be demonstrated.

a. Anything that has an a in the middle will get HALT.

b. Anything that gets to HALT has an a in the middle.

Your answer should be a list of the states in the TM, along with an explanation of the meaning of each state (in English).

3. Build a TM that accepts the language ODDPALINDROME. Submit at least four traces, along with your TMs, that meet the following criteria. Trace two strings that are accepted, demonstrating two different scenarios. Trace two strings that are rejected, demonstrating two different rejection scenarios. You must explain why your strings are accepted and why they are rejected. You must also explain how each state operates.

4. Build a TM that accepts all strings with more qs than ps. As with question 3, trace two accepted and two rejected strings and include the appropriate explanations.

5. Describe a Turing machine that decides the language

L := {O^(2^n ) : n?0 and n?I^+}

a, a (b,AL) (a,#, L) a, a (b,b.L) (A,A,L) (#,#,L) (a,a, R) (b,b,R) (a,a,R) (b,b,R) (b,H,R) START 4 (a, #, R) (b.b,R) (a,a,R) (#,#,R) (A,A,R) HALT