Sketch of Solutions to Exercises

2.2.1
(# of states) < (# of instructions) . (size of domain)(# of variables) < kmk

2.2.2

2.2.3

(a)

a/a, b/e a/e, b/b |||-- -|||- -- |-| - |- --|| O #/e--|- oO[source]

(b)

b/e||- a/e||- -| |- -| |-| - | a/e -- | b/e||| --||- oO -----|| oO -||||||| oO -|||| a/e|||| -------------- b/c[source]

(c)

b/e||- a/e||- -| |- -| |-| - | a/e -- | b/e||| --||- oO -----|| oO -||||||| oO -|||| a/c|||| -------------- b/e[source]

(d)

1/1, 1/e- -| |-- - | --||| oO[source]

(e)

1/e||| -|||- 0/e, 1/e - | ||||- | O - - -0/e--|| ---0/0| --|| O -- -|| oO |||- --1/e 1/1 --|| ||||0/e, 1/e ---|| ----- || O || - -|||| 0/e[source]

(f)

a/a, b/e-- a/e, b/b|- -|| -- -| |- -- || e/e - | --|| oO -----|- oO[source]

(g)

a/e,-b/e|| a/e, b/e|- a/a, b/b- ||||-||| |- -| |- -| |-| -||-||||||||||| - | e/e| -- | e/e --| y --- e/e ||| O -----|| O ---|-- -- ----- -substring |of-- --|| O -- ||||x||||||| |||||| ---e/e -||||||||||||||| --|| e/e| e/e| e/e --- x |-- O -----|| O -----|- O ---|-- -- -| - |-| -- -| - |substring of|-- -|||- --||| -|||- |||||y|||||| e/a, e/b a/a, b/b e/a, e/b[source]

(h)

a/a, b/b| -|||- a/e, b/e - | ||||- | O - - |a/a---| ---b/b| --|| O -- -|| oO |||-- --b/b a/a --|| -|| a/e, b/e ----| ----- || O || - -|||| a/a, b/b[source]

(i)

b/e, e/b- e/a||- a/e||- -|| -- -| |- -| |-| -- | e/e - | e/e -- | a/e b/e --|| O |----|- O -----|| oO -----|| oO ------- O -------- -------- ------- |-------- e/b --- O ||- e/a[source]

(j)

--||||||||1/1 | --i=2j |||||||| O e/e--|||||||||-- |-| || ---- ||| 1/e -- |- O ---e/e ---||||||||||1/1--|- O --i=3j |-- | -||||||||||-- |1/e ||| ---- 1/e O[source]

(k)

--||||||| 1/1|-- | --||||||| --||- -||||| --|-| -| -|i=2j||-- ||--||||---i=2j||-1- | ---e/1e/e || |1/e ---| ||e/e -||||||||- -|||||||| --|||||||| -- -| -- -e/e|-- -| -||i>2j||--- -|i<2j|--- -||||||||-- -||||||| -| |||| ||||| -|-||| |-| 1/e e/1[source]

(l)

a/e,|b/e-|| -|||||||-- ||||||| -||-|||||-||- -|||||||||||| a/b, b/e, e/a|||| -#a >#b -| -| -| -||||||||a/e-|||||||||||- -||||||||||-- --||-| |- e/e---- |#a=#b |||-e/b ---- |||| --||||||||---||| -#a <#b |||-e/a, e/b ||||||||||| ||-[source]

(m)

-|| Oo --e/1-------- 0, -|| O -||||-- || 0,1|||||||||||||||0/1 || || || |||||||| |||||||||e/0 ||| | ||| |||||||||| |||||||||| 1/1 | ||| 1/0 ||||||||||| O ||-- | || 0/0 -----------||0,0 ||||0/0 |||----------- | --||- O --------||| | 3(x1...xn) = 0x1x2...xn -,- ----------||- 0/1 |0/1 | 1/1 |||----------- + | ||| -----|| O x x ...x 0 | || ||1,0 1 2 n |1/1 || ---- O -----------||- O | ||| 0/0 ---- Ci - 1,Xi - 1 Ci, Xi || ||| ----1/0 || ---- O ---------e/0---------|| O | 1,1- -- -- --||| 1/10[source]

(n)

( ) ( ) ( ) 0 /0, 1 /0, 1 /1 0 -||||- 1 0 Oo |||| e/e-------|| 0- ---------- |--(0) --||- eO ----- (1) --|1 /1 ----e/e---0 /0 - ( ) ----|| O xi 1| |-- C O ---yi--|-CO |- -(0) (0) (1 ) i- 1 i --| 0 /1, 1 /0, 1 /1[source]

2.2.4

2.2.5

2.2.6 (q00101, e) |- (0q1101, a) |- (01q001, aa) |- (010q11, aaa) |- (0101q2, aaa)

2.2.7