Problem 1 A language L C * over a finite alphabet is said to be regular if there exists a finite automaton A such that L-C(A). Here L(A) {w E * | w is accepted by A} . Answer the following questions. (1) We fix an alphabet by = {a, b). For the language L1 below, present a nondeterministic finite automaton (NFA) Al such that. C(A) = L1, and the number of states of Al is not greater than 4 Li-{w E * l there is a character I E that occurs more than once in w} (2) Assume that is a finite alphabet. Prove the following: any finite language L = {w1 , . . . , un} is regular. Here n is a nonnegative integer. (3) We fix an alphabet by = {a,b). For the language L1 in Question (1), present a deter- ministic finite automaton (DFA) A2 such that: C(Ag) = * \L1, and the number of states of A2 is not greater than 5. Here * \ Li denotes the complement of L1 L'. (4) Give a decision procedure for the following problem, and explain it briefly. Input nondeterministic finite automaton A. Output whether the language C(A) is an infinite set or not