Finite State Machines 2

The top finite state automaton will always reach an end state when the remainder of the total number of 0's when divided by 2 is 0, the number of 0's will always be a multiple of two.

The bottom automaton can in fact yield an odd number of 0's, however it will always have an even number of 1's.

The string which matches neither of these criteria is 1000, as it has both an odd number of 1's and 0's. Therefore it can not be generated by this automaton.

For the above question, the NDFA accepts "01" or "10" . So it has to end with either "01" or "10", no matter the given string.

To determine if a string can be generated by this state machine, trace through the diagram and see if there exists a path that contains the string AND ends in an accept state (in this example, S1 and S3 are accepting states).

Here S0 is the starting state and we have two acceptable states i.e S1 and S3. For each string check by starting from both S1 and S3 (since we can shift to any state from the S0 state) . If the string can be generated then we should end at an acceptable state.