Homework #3

1.  Consider the toy shown below.  A marble is dropped in at A or B.  Levers
    x, y, and z cause the marble to fall either to the left or right.  Whenever
    a marble encounters a lever, it causes the lever to change state, so that
    the next marble to encounter the lever will take the opposite branch.

                  | A |        | B |
                  |   |        |   |
                  | x |        | y |
                 /  /  \      /  /  \
                /       \    /       \
               /   /\    \  /    /\   \
              /   /  \    \/    /  \   \
             /   /    \  z /   /    \   \
             \   \    /   /    \    /   /
              \   \  /    /\    \  /   /
               \   \/    /  \    \/   /
                \       /    \       /
                   \     /      \     /
                  |   |        |   |
                  |   |        |   |
                  | C |        | D |

     a) Model this toy by a DFA.  Denote a marble in at A by a 0-input and a
      marble in at B by a 1-input.  A sequenc eof inputs is accepted if the
      last marble comes out at D.

     b) Describe the set accepted by the DFA.

     Solution:

      a) M = ({A,B,C,D,E,F,G,H,I,J,K,L}, {0,1}, delta, {A}, {A,B,I,J,K,L})
         delta(A,0) = E       delta(A,1) = D
         delta(B,0) = F       delta(B,1) = A
         delta(C,0) = G       delta(C,1) = B
         delta(D,0) = H       delta(D,1) = I
         delta(E,0) = C       delta(E,1) = H
         delta(F,0) = D       delta(F,1) = J
         delta(G,0) = A       delta(G,1) = K
         delta(H,0) = B       delta(H,1) = L
         delta(I,0) = G       delta(I,1) = B
         delta(J,0) = C       delta(J,1) = H
         delta(K,0) = D       delta(K,1) = J
         delta(L,0) = A       delta(L,1) = K

         Key:  State A corresponds to lever x,y,z positions ///
         Key:  State B corresponds to lever x,y,z positions //\
         Key:  State C corresponds to lever x,y,z positions /\/
         Key:  State D corresponds to lever x,y,z positions /\\
         Key:  State E corresponds to lever x,y,z positions \//
         Key:  State F corresponds to lever x,y,z positions \/\
         Key:  State G corresponds to lever x,y,z positions \\/
         Key:  State H corresponds to lever x,y,z positions \\\
         Key:  State I corresponds to lever x,y,z positions /\/
         Key:  State J corresponds to lever x,y,z positions \//
         Key:  State K corresponds to lever x,y,z positions \/\
         Key:  State L corresponds to lever x,y,z positions \//

      b) Two possible descriptions are
         All strings ending in a 1, where the number of 1s is even.
         All strings of length X that either end in a 1 or have an
            even number of 0s where X mod 4 = 0, or
            (X-3) mod 4 = 0 (X = 3, 4, 7, 8, 11, 12, ...).

2.  Recall (part of) the Roman numeral system:  I = 1, V = 5,
X = 10, L = 50, C = 100.  Recall also that in a valid Roman numeral,
strings such as IIIII or VV are not allowed, since there are alternative
representations using larger values, such as V and X, respectively.

Draw a DFA that accepts exactly the set of valid Roman numerals between
1 and 100 that are strictly ordered:  that is, no letter may appear
after a letter that has a smaller value.  Thus 9 must be represented by
VIII rather than by IX.  The alphabet for your DFA should be
{I, V, X, L, C}.  You should adopt the convention that edges not
drawn lead to a unique "dead" or "trap" state, which is nonaccepting,
and which has edges leading back to itself on any input.
Also, be sure that your DFA doesn't accept any numeral with value 101 or more.

   Solution:  The DFA for strictly ordered Roman numerals is defined below.
Transitions not indicated go to a rejecting state.  All states, except the starstate, are final (accepting) states.

    delta(s,C) = C    delta(s,L) = L          delta(s,X) = X
    delta(s,V) = V    delta(s,I) = I
    delva(L,X) = X    delta(L,V) = V          delta(L,I) = I
    delta(X,X) = XX   delta(X,V) = V          delta(X,I) = I
    delta(XX,X) = XXX delta(XX,V) = V         delta(XX,I) = I
    delta(XXX,X) = XXXX delta(XXX,V) = V      delta(XXX,I) = I
    delta(V, I) = I
    delta(I, I) = II  delta(II, I) = III      delta(III, I) = IIII

3.  Give a NFA that accepts the following language over {0,1}:  the set of
strings such that some two 0s are separated by a string whose length is 4i, for
some i >= 0.

    Solution:

     0,1
    +--+
    v  |
    +--+ 0  +--+ 0  +====+
    |q0|--->|q1|--->||q5||
    +--+   /+--+^   +====+
       0,1/      \0,1
       v        \
       +--+      +--+
       |q2|      |q4|
       +--+      +--+
          \       ^
        0,1\     /0,1
          v   /
          +--+
          |q3|
          +--+

4.  Describe in English the languages accepted by the deterministic finite
    automata shown below.

               b             a
         +----------+===+---------+
        /      a    ||*||          \
       /   +------->+===+           \
      |   /                          |
      v  /                           v
      +-+                           +-+
   -->|*|                           |*|
      +-+                           +-+
         \                         /
          \    b           a,b    /
           +-------->+-+<--------+
                     |*|
                     +-+
                     | ^
                     | |
                     +-+
                     a,b

    Solution:  The set of all strings beginning with an a and followed by
    any number of ba pairs.

5.  Problem 2.2.1 parts a and b from the textbook.

    a)

       +===+   a    +-+   b    +-+   a    +-+
    -->||*||------->|*|------->|*|------->|*|
       +===+        +-+        +-+        +-+
         ^ ^         |          |
       a | | b       | e        | b
         |  \        |          |
         |   \       v          |
        +-+   +-----+-+         |
        |*|<--------|*|<--------+
        +-+    b    +-+

     (i) aa
    (ii) aba
   (iii) abb
    (iv) ab
     (v) abab


     b)
                   b
                  +-+
                  | |
                  v |
       +-+   b    +-+   b    +===+
    -->|*|------->|*|------->||*||
       +-+        +-+        +===+
                   |
                 e |
                   |
                   v
                  +-+        +===+
                  |*|------->||*||
                  +-+   a    +===+
                  ^ |
                  | |
                  +-+
                   b

       (i) ba
      (ii) ab
     (iii) bb
      (iv) b
       (v) bba

    Solution:
       a) (i)   no
        (ii)  yes
        (iii) no
        (iv)  yes
        (v)   yes

       b) (i)   yes
        (ii)  no
        (iii) yes
        (iv)  no
        (v)   yes