A finite automaton reads a word one symbol at a time. The state must remember enough about the prefix already read to decide what to do with every possible continuation. We will build a machine rather than guess a diagram, then prove that it recognizes the intended language.
A precise machine
Definition 6.1.1
(Deterministic finite automaton)
A deterministic finite automaton (DFA) is a tuple : is a finite set of states, is an alphabet, is a total transition function, is the initial state, and is the set of accepting states. Totality means that every state has a specified transition for every input symbol.
For a word , let denote the state reached by reading all of from . In particular for the empty word, and . The automaton accepts exactly when .
A missing transition is not an implicit rejection unless a rejecting sink state and its transitions have actually been supplied.
Track two parity bits
Let contain precisely the binary words with an even number of s and an even number of s. Use states , where the first letter records the parity of the count of s and the second that of s. Start at and accept only . The transitions are:
| State | Read 0 | Read 1 |
|---|---|---|
| EE | OE | EO |
| EO | OO | EE |
| OE | EE | OO |
| OO | EO | OE |
Worked example 6.1.2
(Tracing three words, including the empty word)
Reading gives , so it is accepted: it has two s and two s. Reading ends at , so that word is rejected: its count of s is even but its count of s is one. The empty word is accepted without reading anything, because the machine stays in ; it contains zero occurrences of either symbol, and zero is even.
Proposition 6.1.3
(The parity machine recognizes L)
For every binary word , the state records the parity of the number of s in in its first letter and the parity of the number of s in in its second letter. Consequently the machine accepts if and only if .
Proof
(Induction on the length of the word)
For both counts are zero, hence even, and . Assume the statement for . Reading in the table above changes exactly the first letter of the state (, ) and keeps the second; reading changes exactly the second letter (, ) and keeps the first. The word has one more than and the same number of s, and is analogous, so the statement holds for . By induction it holds for every finite word.
The only accepting state is , so the machine accepts exactly when both counts are even. This proves both directions: no word outside is accepted, and no word in is rejected.
Proof X-ray
Why the invariant must be the whole state
The induction cannot be run on the claim itself. Knowing that is rejected does not tell us whether is accepted, as the counterexample below shows. The statement has to be strengthened to the full pair of parities, which is exactly what the state stores. With that strengthening the acceptance claim becomes an equality of states, , and a single argument gives both inclusions.
The eight table entries enter the proof only through two uniform facts: reading flips the first letter, reading flips the second. That is why one induction step covers all four states at once. Totality of is used silently, since must be defined for every word. If a single entry were wrong, say on led to instead of , the invariant would already fail on the prefix : it has one and two s but would end in instead of .
The same machine has a second description. Identify with the pairs of integers modulo .
Concept lensAlgebraic
States as sums modulo 2
Under this identification, reading adds to the state and reading adds ; checking the eight table entries confirms it, for example . Hence after reading the state is the sum of the letter vectors,
where is the number of occurrences of in . Addition is commutative, so reordering the letters of cannot change the state: and reach the same state. The acceptance condition says that this sum is the zero vector.
Why four states are necessary
Definition 6.1.4
(Distinguishable words)
Let be a language. Two words and are distinguishable for if there is a word such that exactly one of and belongs to .
Proposition 6.1.5
(Four states are necessary)
Every DFA that recognizes has at least four states.
Proof
(Four pairwise distinguishable prefixes)
Each parity pair is reachable: , , , and reach , , , and respectively, so these four words have four different parity pairs. Take two of them, and , with different parity pairs. Append to both the same suffix containing one if has odd zero parity and one if has odd one parity. That suffix makes even in both coordinates. Adding the same suffix to flips the same coordinates, so still differs from in at least one coordinate and has at least one odd parity. Exactly one of and lies in , so and are distinguishable.
Now let be any DFA recognizing . If two of the four words reached the same state of , then for every suffix the words and would also reach the same state, hence receive the same verdict, contradicting distinguishability. So the four words reach four different states of . The four-state machine above is therefore minimal. This is a proof about all DFAs for , not merely a failure to find a smaller picture.
Worked example 6.1.6
(A distinguishing suffix for two prefixes)
The prefixes and reach and . The first has odd parity of s, so take . Then has two s and no , so it belongs to , while has one and is not in . A machine that merged these two prefixes would give both and the same verdict, which is false.
Counterexample mode
Equal verdicts do not allow merging
Suppose a claim says that two prefixes may share a state whenever both are rejected. The prefixes and are both rejected, since each has one odd count. Yet appending gives but (one and one ). The two prefixes behave differently on one continuation, so a correct machine must keep them apart. Two prefixes can share a state only when every continuation gives them the same verdict.
Worked example 6.1.7
(The same argument for a different invariant)
Let be the binary words whose number of s is divisible by . A machine with states (the number of s modulo ), where reading adds one modulo , reading changes nothing, start state and accepting set , recognizes by the same induction. The prefixes , , are pairwise distinguishable. The suffix separates from the other two: has three s and lies in , while has four and has five. The suffix separates from : the word has three s, and has four. Hence three states are necessary, and the machine shows that three suffice. The empty word is accepted since zero is divisible by .
Common mistake
(Do not confuse a state with the last symbol)
The state says that the total number of s so far is even and the total number of s is odd. It does not say which symbol was most recently read. Different prefixes such as and can reach the same state because all their possible continuations have the same acceptance behavior.
Common mistake
(Even length is not enough)
A word of even length need not lie in . The word has length two, but it has one and one , so both counts are odd. A machine remembering only the parity of the length merges with and cannot tell from , although only is in .
Practice
Quick check
(Trace and . Which are accepted?)
Follow the transition table one symbol at a time.
Solution · Answer
goes , so it is accepted. goes , so it ends in and is rejected.
Quick check
(Which suffix distinguishes the states and ? Explain using the acceptance of both resulting words.)
Try the shortest suffixes.
Solution · Answer
The suffix takes to and to ; only the former is accepting.
Quick check
(If the accepting set changes to while transitions remain unchanged, describe the new language.)
Read off what the first letter of the state means.
Solution · Answer
The first parity must be even, while the second may be either value. The language is all binary words containing an even number of s.