3. (20 points) Why is every finite language a regular language? Fill in the missing parts of the proof below, in steps (a) through (f). a. A language is b. A string is a sequence of chosen from a set called the The latter is usually denoted E. C. A single string is a language (a set) with one element (the string). A single string is a regular language because we can make an NFA that accepts the one string in the language and nothing else. E.g. if the string was "oboe, the NFA would look like this: d. A regular language is a language that, by definition, e. We know that regular languages are closed under union, so we could conclude our argument by stating that a finite collection of strings is a union of sets that each contain a single string. But we are hardcore and are going to argue instead that we know how to make an NFA that accepts the union of what a bunch of other NFAs accept. Using Thompson's Construction, here's an example of an NFA that accepts ["oboe"} U {"bo"}: f. We could extend our NFA from the previous step by repeatedly using Thompson's Construction to add more strings. Since the result is an NFA, the finite set of strings is accepted by an NFA, and is thus regular. We note that our proof here relied on the fact that we started with a finite set of strings. If we had an infinite set of strings, then how could we even use Thompson's Construction? The construction process would take forever and generate this many states (i.e. not a finite state machine): 4. (20 points) Prove that the language P = { wxw w {0,1} and x (0,1} } is not regular by using the Pumping Lemma for Regular Languages