Problem Set #2, CS 154, Spring 2005

Problem Set #2

Problem 2 is worth 20 points. The other two problems are worth 10 points each.

Find regular expressions for
1. The set of strings over {0,1,2,3} where all 0's come before all 1's or all 2's come before all 3's.
2. The set of strings over {0,1,2,3} where all 0's come before all 1's and all 2's come before all 3's.
Given the two regular expressions r₁ = (10)* and r₂ = 1(01)*0, find
1. An ε-NFA that accepts L(r₁) and another that accepts L(r₂).
2. Equivalent DFAs for each of the ε-NFAs above. Use the construction of Section 2.5 of the text (which was presented in class).
3. The minimal DFAs that are obtained from these two DFAs by applying the minimization algorithm described in class (this isn't quite the same algorithm as the one described in the text).
In the third cases, trace the behavior of minimization algorithm. 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.

Use the algorithm described in class to find a regular expression for the language that is accepted by the DFA with transition table given below.