Assigned: | Monday, September 16 |
Due: | Monday, September 23 |
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).
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.
Give a regular expression that represents each of the following languages over alphabet Σ = {a, b, c}.
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.)
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.