1. Prove that every finite language is regular. Hint: Give a constructive proof that explains how to start with a finite language (set of strings) Aand then build an NFA that accepts any string in A. There is a brute force style of NFA that ends up with a total of [Q] = 1 + lw|states. WEA Sketch the NFA corresponding to A = {00, 11, 101}. 2. If NFAs were restricted to have at most one accept state, would they become less powerful? Let Nbe an arbitrary NFA. Prove that there exists an NFA N'such that N'has exactly one accept state, and L(N) = L(N'). Hint: One way of proving this is to give a constructive proof, where N'has one more state than does N