DFA determining parity (the number of 1's mod 2)
No end-of-input marker: we stop in the state indicating the parity
r1 : even • 0 ->> even.
r2 : even • 1 ->> odd.
r3 : odd • 0 ->> odd.
r4 : odd • 1 ->> even.
r2 : even • 1 ->> odd.
r3 : odd • 0 ->> odd.
r4 : odd • 1 ->> even.
Example
%trace * even • 1 • 0 • 1 • 1.
even•1•0•1•1
odd•0•1•1
odd•1•1
even•1
odd