Assignment

Suppose a particular FA, called FIN, has the property that it had only one final state that was not the start state. During the night, vandals come and switch the + sign with the - sign and reverse the direction of all the edges.

a) Show that the picture that results might not actually be a FA at all by giving an example.

b) Suppose, however, that in a particular case what resulted was, in fact, a perfectly good FA. Let us call this NIF. Give an example of one such machine.

c) What is the relationship between the language accepted by FIN and the language accepted by NIF? Why?

d) One of the vandals told me that if in FIN the plus sign and the minus sign were the same state, then the language accepted by machine will only contain palindrome words. Defeat this vandal by example.