CIS 420/520 Assignment 6
Turing Machines
The problems here are all from the second edition of the Sipser book. If you
are using the first edition, many of the problems are the same, but the numbering
of the problems is not.
Assignments are due at the beginning of class on the due date indicated.
Use machine copy if at all possible - in any case, writing and diagrams
must be neat and legible.
Assignment 6 is due Monday, November 26.
Sipser 3.8 b,c
Give implementation-level descriptions of Turing machines that decide the following
language over the alphabet { 0, 1 }.
-
{ w | w contains twice as many 0s as 1s }
-
{ w | w does not contain twice as many 0s as 1s }
Sipser 3.15 b,c,d,e
Show that the collection of decidable languages is closed under the operation of
-
concatenation.
-
star.
-
complementation.
-
intersection.
Sipser 3.13 (for CIS 520 students)
A Turing machine with stay put instead of left is similar to an ordinary
Turing machine, but the transition function has the form
δ: Q x Γ → Q x Γ x {R,S}.
At each point the machine can move its head right or let it stay in the same position.
Show that this Turing machine variant is not equivalent to the usual version.
What class of languages do these machines recognize?