Sketch of Solutions to Exercises

4.1.1
(˘q0baba$, q0, e) |- (˘bq1aba$, bq1, b)
|- (˘baq1ba$, baq1, ba)
|- (˘baq2ba$, bq2a, ba)
|- (˘baq2ba$, q2ba, ba)
|- (˘baq2ba$, q2Bba, ba)
|- (˘baq3ba$, q3ba, ba)
|- (˘babq3a$, bq3a, ba)
|- (˘babaq3$, baq3, ba)
|- (˘babaq4$, baq4, ba)
4.1.2 (a)

| | | a |+1 b |+1 c|+1 B |a,+1 a |a,-1 a|a,+1 |d |e |e || -||--- | -||-|- | ||-|- Ba|a+,1+1 - --Bb|B0,-1 -- --Bc|B0, -1 -- |- |d -- || |e - | |e - | --||| O ---------|| O ---------| O ----------- O | | --------- | $|0 ---------- |B |B,0 ---------- || |e--------- $||0 oO -|| B||B,0 e[source]

(b)

a |+1 b |+1 B |a,+1 B |B,0 B |B,0 B |b,+1 B ||B,0 B |B,0 |e || , |e , || c||+1 $||0 B||B,0 a|a,-1 B||B,0 b|b, -1 B |ec,+1 c|dc,- 1 ||||- || -||||- | |-- -| $|0 -- -| $||0 |- -- B |B, -1 | -- B||B,0 - -- BB|BB,,--11 -- -- BB|BB,,00 -- | |e -- || |e --|| O ----------------|| O ----------------|| oO[source]

(c)

a |+1 b |+1 B |a,+1 B |B,0 B |B,0 B |b,+1 B ||B,0 B |B,0 |e || , |e , || c||+1 $||0 B||B,0 a|a,-1 B||B,0 b|b, -1 B |ec,+1 c|dc,- 1 ||||- || -||||- |-- -| $|0 -- -| |- -- B |B, -1 | -- - -- BB|BB,,--11 -- -- -- | |e -- || else --|| O ----------------|| O ----------------|| oO[source]

(d)

| | | | | | a |+1 b |+1 a||+1 b|+1 a|+1 b |+1 B |a,+1 B |b,+1 B |B, -1 b|B, -1 B||B,0 B |B,0 B |a,+1 B |B,0 B |B,0 B||B,0 a||B, -1 B||B,0 |a , |e||| |e , |e||| |e , |e||| | -|| |- * |0 -|| |- * |0 || -- $ |0 - - B |B, -1 - - B |B,0 - -- B |B,0 |- -- B |B,0 |- |-| B |B, -1 |- |- B |B,0 --|| ------||e---------|| -------|e---------|- -------|e---------||- O O O oO[source]

(e)

| | a|+1 a|-1 B |a,+1 a||a,0 ||e |a -||-|- | -||-|- - |- B$|B-,1-1 -- |- - | |e - | --|| O ------------||- O || |||- --- c/|0 a$a-,10 -|||-- --- B |B,0 ||e --- -- --- |e --- --- || | --- | --||-- /c|+1$||0 --- *|0 ---|| a|a,-B1|B,0 --| B |B,0 O |--------e---|e--------------|- O -----|e-----||- oO | -- | - -- - -| - -- ||- -- || |-|| ||-|| a|+1 *|0 a||a,0 B |B,0 |b |b[source]

4.1.3 (a)

|| || *|0 *||0 | || a|a,-1, b |b,-1, a||+1 b||+1 *||+1 | B |a,+1, B |b,+1 B |B,0 |||- a|+1 b |+1 -| |- * |0 || |- B |a,+1, B |b,+1 - | B |B, -1 - | --||| O ------------------||- O ------------------||- O | | | || |B*|B0,+1 || oO -|------------------ O | | - $|0 -| |- B | B,0 |||| | a||+1 b|+1 a |a,+1, b |b,+1[source]

(b)

| | | | a |+1 b |+1 a|+1 b||+1 B |a,+1 B |B,0 a|a,-1 * |*,0 B |d,+1 ,B |d,+1, d |d,-1 ,d |d,-1 , c||+1 c|+1 B |B,0 *|*,0 B |d,+1 d |d,-1 -|-|-- *|0 ||-|- $||0 - |-- B ||B,-1 -- |- B |B,0 - | B |B,-1 - | B |B,0 --||- O ------------------||- O ------------------|| oO[source]

(c)

a|+1 b |+1 a|+1 b |+1 B||a,+1 B |B,0 a|a, -1 * |*,0 B |d,+1 , B |d,+1, d |d,-1 , d|d,-1 , | c|+1 c|+1 *|+1 B||B,0 *|*,0 B||B,0 B |d,+1 d |d,-1 d |d,-1 ||-|- || ||-|- || ||-|- -- |- B $B0, -1 - |- Ba|+B1,0 - |- - | B |B,-1 - | d |d,-1 - | --||- O ------------||- O ------------||- O --- $ |0 | --- a |a,0 | | ---B |B,0 | $ |0 --- |B |B,0 ---- |B |B,0 --| || oO[source]

(d)

(e)

a |+1 b |+1 B |a,+1 a |a,-1 |||-- | ||||- || -- |-- b||0 - -- $|0 O --B-|B,-1--| O --B-|B,0---|- oO || | || | | | | | a||+1 | | c||0 | B |a,+1 | |B |B,+1 | | c|+1 || | B ||c,+1 | | --|| O ----------||| O $||0 | || |- --- B |B,0 | | ||||| --- d||0 | c|+1 | | ---a a/ -1 | a |c,+1 | c||+1 ---- | |B c,+1| --- | ||| d||0 --| | | --||| O --B-|B,--1-|--O ||--d||+1 c|+1 -||| ||||c|c,-1 B |c,+1 ||[source]

(f)

| | b|+1 a|+1 a |a,+1 | a |a,-1 | -|||- a|+1 -|||- Ba|+a1,0 - ||-B |a,-1 -- ||| --||- O -----------|- O -||---------- O | | | ----|----- || $|0 ||| b||0 |B| |B,0 || || B |B,+1 || ||| $||0 -|| |- B |B,0 oO[source]

4.1.4

(a) Given two Turing tranducers M 1 and M 2 a Turing transducer M 3 can compute R(M 1) U R(M 2) by nondeterministically choosing to follow either M 1 or M 2 on a given input.

(b) Given two Turing transducers M 1 and M 2 a Turing transducer M 3 of the following form computes R(M 1)R(M 2). M 3 on a given input x follows a computation of M 1. Upon reaching an accepting configuration of M 1 the Turing transducer M 3 switches to follow a computation of M 3 on x.

(c) Consider any Turing transducer M 1. The reversal of R(M 1) can be computed by a Turing transducer M 2 that processes its input in reverse order.

4.1.5 inputs. The complement of L(M 1) is accepted by a Turing machine M 2 that on a given input x tries all possible sequences of t moves of M 1 on x, for t = 0, 1, ... . M 2 accepts x if it finds t such that all sequences correspond to nonaccepting computations of M 1. M 2 rejects x if it encounters an accepting computation of M 1.

4.1.6 A linear bounded automaton M on input x can enter at most s . (|x| + 2)(|G||x| . |x|)m different configurations, where s denotes the number of states of M, -- G -- denotes the number of symbols in the auxiliary work tape alphabet of M, and m denotes the number of auxiliary work tapes of M.

Hence, M can be modified to count the number of configurations being reached, and to force a computation to halt in a nonaccepting state upon reaching the above bound on the number of moves.

4.1.7 Consider any Turing transducer M 1. Denote by {q0, ..., qf } the set of states of M 1, and by m the number of auxiliary work tapes of M 1. M 1 is equivalent to an m + 1 auxiliary work tape Turing transducer M 2 of the following form.

M 2 has three states {p0, p1, p2}. p0 is the initial state, and p2 is the only accepting state. M 2 uses the first auxiliary work tape for recording the state of M 1.