Anatomy of a Lean Proof for Software Engineers
10 hours ago
- The problem is to prove a language of 3-row bit columns with bottom row equal to sum of top two rows is regular, from Sipser's textbook.
- The solution constructs a DFA that recognizes the reversal of the language using carry states (0, 1, dead) and adder arithmetic, then uses closure under reversal.
- The formal proof in Lean defines states, transition functions, and a run invariant connecting DFA behavior to binary addition equations.
- Key lemmas include splitting the run, single-step addition, and least-significant-bit arithmetic, proven by induction and case analysis using `decide` and `omega`.
- The final proof applies Mathlib's theorem on regular language closure under reversal to conclude the original language is regular.
- The article highlights how formal proofs require detailed reasoning and that AI tools may reduce the cost of formal verification in the future.