5.3. Let S = {a, b, c, d), and let L be the language consisting of all strings in S* in which at least one of the symbols in Sappears an odd number of times. a. Design an eight-state nondeterministic Fsa for L. Using the tech- niques of Section 2.5.1, construct an equivalent deterministic accepter and eliminate redundant and nonaccessible states. How many states are in the deterministic machine? b. Generalize the result of part a. That is, prove that if S contains n symbols, there exists a 2n-state nondeterministic accepter for L and a 2"-state deterministic accepter for L. *c. Prove that if S has n symbols, no deterministic accepter for L can have fewer than 2" states. [Hint: Show that if M is a deter- ministic accepter for L with fewer than 2" states, there exist input strings 0, y such that (1) both strings lead M to the same state, and (2) some symbol in S occurs in o an odd number of times and in y an even number of times. Show that the existence of such strings implies incorrect behavior on the part of M.] 5.3. Let S = {a, b, c, d), and let L be the language consisting of all strings in S* in which at least one of the symbols in Sappears an odd number of times. a. Design an eight-state nondeterministic Fsa for L. Using the tech- niques of Section 2.5.1, construct an equivalent deterministic accepter and eliminate redundant and nonaccessible states. How many states are in the deterministic machine? b. Generalize the result of part a. That is, prove that if S contains n symbols, there exists a 2n-state nondeterministic accepter for L and a 2"-state deterministic accepter for L. *c. Prove that if S has n symbols, no deterministic accepter for L can have fewer than 2" states. [Hint: Show that if M is a deter- ministic accepter for L with fewer than 2" states, there exist input strings 0, y such that (1) both strings lead M to the same state, and (2) some symbol in S occurs in o an odd number of times and in y an even number of times. Show that the existence of such strings implies incorrect behavior on the part of M.]