Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Comp335 Introduction to Theoretical Computer Science

Winter 2023

Assignment 4. Due April 17.

1.   (a)  Construct a Turing machine for the language

{xay  : x, y e {a, b}* , ∣x∣ = ∣y∣}.

(b)  Construct a Turing machine for the language

{an b2nc3n : n > 1}.

(c)  Construct a Turing machine that creates a copy of its input string to the right of the input with a blank separating the copy from the original.

2.  Consider a nondeterministic TM whose tape is infinite in both directions.  At some time, the tape is completely blank, except for one cell, which holds the symbol $. The head is currently at some blank cell, and the state is q .

(a) Write transitions that will enable the NTM to enter state p upon reading $.

(b)  Suppose the TM were deterministic instead.  How would you enable it to find the $ and

enter state p?

3.  Give a complete encoding of the TM

A = ({q1 , q2 , q3 }, {a1 , a2 }, δ, B, {q3 }),

where the transition function δ is given by δ(q1 , a1 ) = (q1 , a1 , R), δ(q1 , a2 ) = (q3 , a1 , L), δ(q3 , a1 ) = (q2 , a2 , L).

4.  Show that the language of codes for TM’s M that, when started with a blank tape, eventually write a “1” somewhere on the tape is undecidable.

5. For each of the following instances (A, B) of Post’s Correspondence Problem, determine if it has a solution or not. If you think (A, B) has a solution, give one, and if you think (A, B) does not have a solution, provide reasoning to justify your claim.