Pleasedo these questions. It's about the theory of computation.

For problems 1-3, describe a DFA that accepts the given language. Describe in plain language what is the purpose of each state. It will probably help to give thoughtful names to the states. 1. (xE {a, b last 5 characters ofx are not ababb). 2. (x E [o, 1)* | bin(r) is 1 more than a multiple of 5) bin(x) is the function from lecture, defined recursively as: bin(c)-0 bin(wc 2 bin(w)+c, fora w 0,1 and c E (0, 1) 3. {xE {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. 4. In lecture, we defined the extended transition function . : Q x Q recursively in terms of , via: 6" (q, wc) = (N* (g, w), c), for all w E * and c Using this definition, prove that *(q, xy) = "(6"(g, x), y), for all x, y e In other words, the state that you get to by starting at q and reading xy, is the state that you get to by starting at q, reading x, then reading y. Hint: Use induction on the length of y. You can follow the examples for induction on strings from Erickson's notes section 1. However, in this case you should do induction by adding a character to the end of y (not beginning of y as in the Erickson examples). This makes things match the recursive definition * better