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 .

(d) Prove that for every k, no DFA with fewer than 2^k states can recognize C_k.