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