2.(Number of states) Let = {a, b}. For each k 1, let C_k be the language consisting of all strings that contain an a exactly k places from the right-hand end. Thus C_k = ^*a^k-1 .

(c) Find 2^k strings on which every DFA recognizing C_k must enter different states. (Hint: Start by finding 2 such strings).