= we defined the language Sa of strings whose k+1'st to last letter exists and is a. (Here k is an arbitrary natural.) Design an NFA for this language with k +2 states and apply the Subset Construction to it. Minimize your DFA if necessary. You now have an example that will prove a theorem of the following form: For every n with n > no, there exists a language that has an n-state ordinary NFA and whose minimal DFA has (n) states. You get to pick no, and the function (n) should be as large as you can make it. Solution: 'Let k be a natural, let = (a, b), and consider the regular language Ska, consisting of all those strings whose l'st to last letter exists and is an a. Find the minimal DFA for each such language Sk, and prove that it is minimal. AANU