Computer Science 4602, Fall 2019
Assignment 2

1. Draw a transition diagram of an NFA for each of the following languages with the given number of states. Label each state by an integer (from 1 to n for some n).

   1. {w ∈ {a, b}^* | w ends on bb} with three states
   2. {w ∈ {a, b}^* | w contains an even number of a's or w contains exactly two b's (or both)} with six states
   3. Language a^*b^*aa^* over alphabet {a, b} with three states

2. Use the subset construction to convert each of the NFAs that you got in the previous exercise to a DFA. Label each state of the DFA by the set of states of the NFA that it corresponds to. Don't forget to include a state for {}, if it is needed. Remember that a DFA must have exactly one transition out of each state for each symbol of the alphabet.

3. Give a regular expression that represents each of the following languages over alphabet Σ = {a, b, c}.

   1. {w ∈ Σ^* | w begins with a and ends with b}
   2. {w ∈ Σ^* | w has at least three c's.}
   3. {w ∈ Σ^* | w has aab as a contiguous substring}
   4. {w ∈ Σ^* | w does not have aab as a contiguous substring}
   5. {w ∈ Σ^* | w is any string except ab and bba}
   6. {w ∈ Σ^* | w ends with cc}
   7. {w ∈ Σ^* | w does not contain ac as a contiguous substring.}

4. Prove that the class of regular languages is closed under complementation. (The complement L of a language L over alphabet Σ is defined to be Σ^* − L.)

5. If w is a string then stutter(w) is the string obtained from w by writing each symbol twice in a row. For example, stutter(abac) = aabbaacc and stutter(aabb) = aaaabbbb.

   If L is a language then stutter(L) is defined to be {stutter(w) | w ∈ L}.

   Prove that the class of regular languages is closed under stutter.