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 sequence of inputs is accepted if the
        last marble comes out at D.

     b) Describe the set accepted by the DFA.


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.


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.


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

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

5.  Which of the following strings are accepted by these nondeterministic
    finite automata?

    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