[SOLVED] CSC173 Homework 31 Turing Machines Web

CSC173: Homework 3.1

Turing Machines

1.  Let M = ⟨Q,Σ , Γ,δ, q0 , q accept , qreject ⟩, where

Q = {q0 , q accept , qreject }

Σ = {a, b}

Γ = {a, b, ⊔}

and δ is given by the following table:

(a)  Draw M’s transition function as a state diagram.

(b) Trace the computation of M on input aabbbaa.

(c)  Describe informally (in English) what M does.

2.  Let M = ⟨Q,Σ , Γ,δ, q0 , q accept , qreject ⟩, where

Q = {q0 , q1 , q accept , qreject }

Σ = {a}

Γ = {a, ⊔}

and δ is given by the following diagram:

(a) Give M’s transition function as a table.

(b) Trace the computation of M on inputs aa and aaa.

(c)  Describe informally (in English) what M does.

3. Trace the execution of the machine M2  from Sipser Example 3.7 on each of the following inputs:

(a)  0

(b)  00

(c)  000

(d)  000000

4. Trace the execution of the machine M1  from Sipser Example 3.9 on each of the following inputs:

(a)  11

(b)  1#1

(c)  1##1

(d)  10#11

(e)  10#10

5.  Design and write the formal definition of a Turing  machine with input alphabet {a, b} that scans to the right until it finds two consecutive a’s and then accepts.

(a)  Does your machine halt on all inputs?

(b)  If not, could you design one that does halt on all inputs?

(c)  Can this language, the set of strings that contain two consecutive a’s, be decided by a simpler type of machine (that we have seen in this class)?