Problem Set #2

CS 154
due October 7, 2004

Problem 2 is worth 20 points. The other two problems are worth 10 points each.
  1. Find regular expressions for
    1. The set of strings over {0,1,2} where all 1's come before all 2's
    2. The set of real number literals in a hypothetical programming language, where a real number literal consists of an optional sign followed by a mantissa followed by an optional exponent. Assume that the sign can only be a minus sign, and that the exponent consists of the letter E followed by an optional minus sign followed by one or two digits. Assume that the mantissa is a string over {0,1,2,3,4,5,6,7,8,9,.} with at most one dot and at least one digit. Assume that leading zeros are acceptable. So for example, the strings -123E6, 12.34E05, 023. and .67E23 would be acceptable, while .E7, 2.3.4E24, +6E14, E27, 2.56E-, .34E+5, and 5.2E057 would not be.

  2. For the regular expression r = 1(01)*0 + (10)*1, show
    1. An ε-NFA that accepts L(r)
    2. The DFA for L(r) that is obtained by applying the algorithm of Section 2.5 of the text
    3. The minimal DFA that is obtained from the previous DFA by applying the minimization algorithm described in class (or in the text)
    Trace the behavior of the appropriate algorithms in the last two cases. In the first case, you needn't provide the exact ε-NFA that the algorithms of chapter 3 would construct from the regular expression; however you will need to be careful if you do not.

  3. The DFA given by the table below accepts those strings over {0,1} that are multiples of 4 when interpreted as binary numbers (including ε). Use the algorithm described in class to find a regular expression for the language that is accepted by this DFA.

     01
    *q0 q0q1
     q1 q2q3
     q2 q0q1
     q3 q2q3