(D-Problems discussed on Wednesday, 17-Apr-2013)
(No Q-Problems! Yeah!)
T11-PP1: (Simple TM programs)
(a) Practice Prob 2 on Section 11.3 of [SG].
(b) Practice Prob 3 of Section 11.5 of [SG].
(c) Problem 8,13 on p.551-2 of Chapter 11 of [SG].
T11-PP2: (Executing a Turing Machine Program)
Run the TM program for Odd Parity Bit (Notes, slide 20)
on the two input strings given in slide 19.
T11-D1: (TM) Problem 16 on p.552 of Chapter 11 of [SG].
T11-D2: (TM) Problem 17 on p.552 of Chapter 11 of [SG].
T11-D3: (TM) Problem 10 on p.551 of Chapter 11 of [SG].
Review: (Review of All Topics)
You can freely ask question on any topics.
No Q-problems to hand in this week!
(Note: But some Q-like problems for you to try on TM.
For this tutorial, I call them Q'-questions. No need to turn
in solutions for Q'-questions.)
T11-Q'1: (TM)
Problem 24 on p.552 of Chapter 11 of [SG].
(Note: This is related to the Problem 17.)
T11-Q'2: (10 points) (TM)
Problem 25 on p.552 of Chapter 11 of [SG].
T11-Q'3: (10 points) (TM, modified from past final exam.)
Draw a state diagram for a Turing machine that takes a binary string
as input and inverts all the bits in the stringóthat is,
changing the 0s to 1s and the 1s to 0s
(as in a bit inverter seen in the lectures)
and also append an odd parity bit at the end of the inverted string.
(The output string consists of the inverted input string and
an extra parity bit. The output string has odd parity.)
sample input string: ...b01101b...
sample output string: ...b100101b...
A9-2013: (Something on TM, maybe later or not at all…)