edited by
952 views
1 votes
1 votes
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.

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

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

(iii) What is the relationship between the language accepted by FIN and the language accepted by NIF as described in part (ii)? Why?

(iv) One of the vandals told me that if in FIN the plus state and the minus state were the same state, then the language accepted by the machine could contain only palindromic words. Defeat this vandal by example.
edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
1
nida nadeem asked Feb 28, 2017
1,442 views
build an fa that accepts language of all strings of length 4 or more such that next to last (second last) letter is equal to the second letter of input string
0 votes
0 votes
0 answers
2
Vineeta asked Sep 11, 2016
672 views
0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4