print · source · login   




The DFA below has a binary alphabet and accepts all words that contain an even number of 0s.

Figure 1 The state diagram for M

M = (Q, Σ, δ, q0, F) where


The state S1 represents that there has been an even number of 0s in the input so far, while S2 signifies an odd number. A 1 in the input does not change the state of the automaton. When the input ends, the state will show whether the input contained an even number of 0s or not. If the input did contain an even number of 0s, M will finish in state S1, an accepting state, so the input string will be accepted.