1. True or False. [2 points each] For each incorrect answer, 2 points will be subtracted. The union of any two regular languages is regular If L is any regular language, define PREF(L) to be the set of all prefixes of strings in L. (A (b)I prefix of a string w is a substring consisting of the first k symbols of w for some k.) Then PREF(L) is regular (c)Every subset of a regular language is regular (d) The set of algebraic expressions (those that would be accepted by your high-school math teacher) is a regular language. (e) The set of base 7 numerals that name multiples of 17 is regular 2. Fill in each blank with one word. [5 points each (a) Every NFA with n states is equivalent to a unique DFA, which has at most states. (I want the formula.) (b) According to the principle, if there is a function from A to B, and if A has more elements than B, then there must be at least two elements of A that are mapped to the same element of B (c) We use the principle to prove that a predicate is a tautology by first proving a basis and then proving each case follows from its immediate predecessor