give the state diagram of a finitestate machine on summation

\"give the state diagram of a finite-state machine on summation ={0,1} which accepts any string with an even number of zeros\"

Solution

Ans-

Any program can be thought of as a finite string from a finite alphabet of letters. We can therefore infer that the set of programs is enumerable. By contrast, the set of all functions N N is non-enumerable (see lectures). So there is no surjective map from programs to functions (if there were, then the set of functions would be enumerable). In particular, the map that takes programs to the function they compute is not surjective, and hence there are functions for which there is no programFor each part, we give a transition diagram which is a solution to the problem (and for the first, we give two alternative solutions). Following each diagram is a discussion of the meaning of the states of the machine; you should try to work this out for yourselves before reading. 1. The following is a “conceptually clean” solution, in the sense that each state corresponds to different ending of the string:An alternative solution is given below: 0 start q0 q1 q2 1 0 1 1 0 q0 : String has no trailing zeroes. q1 : String has one trailing zero. q2 : String has two trailing zeroes. 2. Here is a machine which accepts the given language. 1 start q0 q1 q2 1 0 1 0 0 q0 : String contains no 00, and the last symbol was a one q1 : String contains no 00, and the last symbol was a zero q2 : String contains a 00 3. 0 start q0 q1 1 0 1 q q3 2 0 0 1 1 q0 : String contains no 011, and the last symbol was a one q1 : String contains no 011, and the last symbol was a zero