DFA · Regular
Checking a sum, column by column
Each symbol is a column a+b=c of a binary addition, least significant column first. The carry is the only thing to remember, so two states check additions of any length.
The author’s examples, run
ε → accept1+1=0 0+1=0 0+0=1 0+0=0 → accept0+0=0 0+1=1 1+0=1 → accept0+1=1 1+1=0 0+0=1 1+0=1 0+1=1 0+1=1 0+1=1 → accept0+0=1 → reject0+0=0 0+1=0 0+0=1 0+0=0 → reject0+0=1 0+1=1 1+0=1 → reject0+0=1 1+1=0 0+0=1 1+0=1 0+1=1 0+1=1 0+1=1 → reject