Solve the following Theory of Computation question

Problem 4. [Category: Design+Proof] Let Ak{a,b} be the collection of strings w where there is a position i in w such that the symbol at position i (in w ) is a, and the symbol at position i+k is b. For example, consider A2 (when k=2 ). baab A2 because the second position (i=2) has an a and the fourth position has a b. On the other hand, bb/A2 (because there are no a s) and aba/A2 (because none of the a are followed by a b2 positions away). 1. Design a DFA for language Ak, when k=2, you just need to draw the transition diagram. [5 points] 2. Design an NFA for language A2 that has at most 4 states. You need not prove that your construction is correct, but the intuition behind your solution should be clear and understandable. [5 points] 3. (Optional) Prove that the DFA you give in part 1 is correct, that is the DFA recognize the language AK when k=2. [5 points] 4. (Optional) Design a DFA for language Ak using formal definition (by listing states, transitions, etc. and not "drawing the DFA"), the formal definition will depend on the parameter k but should work no matter what k is; see lecture 3 for such an example. 5. (Optional) Prove that any DFA recognizing A2 has at least 5 states. [5 points]