CMSC 330 HOMEWORK EXERCISES #1
Regular Expressions and DFAs

In each of the following problems you are given a language and are asked to produce a regular expression and/or finite automaton for the language.
In some cases you are asked to give either a DFA or regular expression (your choice) and in other cases to give both a DFA and regular expression. When writing regular expressions, use an e to denote the empty string.  Write DFAs in the form of a transition diagram.

The underlying alphabet is S = {a, b}.

The notation #a(w) appearing below means the number of a's occurring in string w.
For example, #a(bbaba) = 2.

1. (Either DFA or Reg. Exp) {w | w begins with abab}.
2. (Either) {w | w ends with abab}.
3. (Either) {w | w begins with ab and ends with ba}.
   (Note: The string aba is in this language!)
4. (Either) {w | either #a(w) is divisible by 3 or w begins with bbb}.
5. (Either) {w | #a(w) º 2 (mod 5) }.
   (Recall that i º j (mod k) if and only if (i-j) is divisible by k.)
6. (Either) {w | #a(w) º 1 (mod 3) and #b(w) is odd}.
7. (Either) {w | #a(w) is even or |w| is even}.
8. (Both DFA and Reg. Exp) {w | aaa is a substring of w}.
9. (Both) {w | aaa is not a substring of w}.
10. (Either)  {w | w contains exactly one occurrence of the substring aaa}.
    (Note: the string aaaa has two occurrences of aaa!)
11. (DFA only) {w | neither aa nor bb is a substring of w}.