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