Describe a DFA that accepts the given language. Describe in plain language what is the purpose of each state.

1. {x {a,b}* | Last 5 characters of x are not ababb}

2. {x {0, 1}* | bin(x) is 1 more than a multiple of 5}.

bin(x) is the function defined recursively as: bin() = 0 bin(wc) = 2 bin(w) + c, for all w {0, 1} and c {0, 1}

3. {x {a,b}* | x contains at least 3 occurrences of the substring aba}.

Overlapping of substrings is allowed. For example, the string abababa should be accepted