Library

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.

carry0carry10+0=0, 0+1=1,…1+1=00+0=10+1=0, 1+0=0,…
The machine as drawn — 2 states, 8 transitions.

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