Please describe as much as possible. Thank you.

2. Describe (but do not fully specify or write down) a deterministic finite automaton whose language is = {we L* Iw has length at least three and the third-to-last and second-to-last symbols in w are different}. When solving this problem you should make sure that the following questions are an- swered: What information does this deterministic finite automaton need to remember (using its states) in order for its language to be ? (Approximately) how many states does this deterministic finite automaton have? 3. Finally, give a much simpler nondeterministic finite automaton whose language is the language defined in the previous question and explain (somewhat informally, and reasonably briefly) your answer is correct. Hint: One of the examples of a nondeterministic finite automaton discussed in the lec- tures on NFA's should be studied. You should find that that there is a nondeterministic finite automaton with only six states that has language . However, you will receive full marks if you give a correct NFA for this language with more states than that and explain why your answer is correct. 2. Describe (but do not fully specify or write down) a deterministic finite automaton whose language is = {we L* Iw has length at least three and the third-to-last and second-to-last symbols in w are different}. When solving this problem you should make sure that the following questions are an- swered: What information does this deterministic finite automaton need to remember (using its states) in order for its language to be ? (Approximately) how many states does this deterministic finite automaton have? 3. Finally, give a much simpler nondeterministic finite automaton whose language is the language defined in the previous question and explain (somewhat informally, and reasonably briefly) your answer is correct. Hint: One of the examples of a nondeterministic finite automaton discussed in the lec- tures on NFA's should be studied. You should find that that there is a nondeterministic finite automaton with only six states that has language . However, you will receive full marks if you give a correct NFA for this language with more states than that and explain why your answer is correct