4. Let I = {a,b}. For each k > 1, let Lk be the language consisting of all strings that contain an a exactly k places from the right-hand end of the string. Thus, Lk = L*ak-1. Describe an NFA with k +1 states that recognizes Lk using only k + 1 states. Prove that for each k, no DFA can recognize Lk with fewer than 2k states. Thus, NFAs can give an exponential improvement over DFAs in terms of memory requirement