Toy DFA

Source: http://www.wikiwand.com/en/Deterministic_finite_automaton

Description

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, Σ, δ, q₀, F) where

• Q = {S₁, S₂},
• Σ = {0, 1},
• q₀ = S₁,
• F = {S₁}, and
• δ is defined by the following state transition table:

The state S₁ represents that there has been an even number of 0s in the input so far, while S₂ 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 S₁, an accepting state, so the input string will be accepted.