Anatomy Of A Lean Proof For Software Engineers

TL;DR

Prime Big Deal Days · Oct 6–7Offer from Amazon

Get school and study supplies delivered free — and shop member deals

• Fast, free delivery on millions of items
• Access to Prime Big Deal Days deals on October 6–7
• Prime Video, Amazon Music and more included

Start your free Prime trial →Free trial for eligible customers · Cancel anytime

As an affiliate, we earn on qualifying purchases.Hide

A post published by Agost Biro walks through formalizing a textbook proof in Lean: a language of three-row bit strings, where the bottom row is the sum of the top two, is regular. The account presents the work as an accessible example of how a mathematical construction becomes a machine-checked proof, while noting that following it requires some background in programming, binary arithmetic and induction.

Agost Biro has published a walkthrough of a Lean formalization showing that a language defined by binary addition across three rows of bits is regular. The post translates a textbook construction—designing a finite automaton and proving that it recognizes the intended strings—into a machine-checkable proof, offering software engineers a concrete example of formal verification in mathematics.

The problem comes from Michael Sipser’s Introduction to the Theory of Computation, third edition. Its alphabet consists of columns of three bits. A word over that alphabet represents three bit rows; the language contains the words for which the bottom row equals the sum of the top two. Sipser’s exercise asks readers to show that this language is regular, and suggests that it is easier to work with the reversed language.

Biro’s account follows that hint by constructing an adder automaton and formalizing the reasoning in Lean. The post’s outline moves from the specification and implementation to an explanation of how proofs work, then details a run invariant, its base case and inductive step, and how the automaton’s acceptance establishes regularity. It closes the argument by relating regularity of the reversed language to regularity of the original language.

The source describes this as a worked example rather than a report of a new theorem or a Lean release. Biro says the proof uses results available in Mathlib, Lean’s mathematical library. The article is aimed at readers comfortable with a modern statically typed language such as TypeScript or Rust, binary arithmetic, basic propositional logic and inductive proofs.

From Automaton Design to Checked Proof

The example matters to software engineers because it makes the structure of formal verification visible. A conventional proof describes why a construction works; in Lean, the specification, automaton and argument must be expressed in a form the proof assistant can check. The post’s focus on a run invariant and the separate base and inductive cases shows how familiar verification ideas—state, invariants and step-by-step reasoning—also appear in a mathematical proof.

That connection does not mean the automaton is itself a software product or that the post reports a practical performance result. Its value is educational: it gives readers a specific account of the work involved in turning an informal constructive argument into a formal one. For engineers considering proof assistants, the example can help clarify both the potential and the effort: Lean checks the stated formal argument, but people still need to define the right problem and supply a proof that connects the construction to it.

The Textbook Problem Behind the Proof

A deterministic finite automaton reads symbols in sequence, updates one of a fixed set of states and accepts or rejects a word according to its final state. A language is regular when some such machine accepts exactly its members. This makes constructing a suitable automaton a standard way to prove regularity.

In Sipser’s exercise, each symbol is a three-bit column, so reading a word builds three aligned binary rows. Addition normally proceeds from the least significant bit toward more significant bits, while the columns in the given word are read in the opposite direction. The exercise’s reversal hint addresses that mismatch. Biro’s post then uses the automaton and a formal argument about its runs to connect the construction back to the language in the question.

What the Walkthrough Does Not Establish

The source is an individual educational post, not an independent evaluation of Lean or a peer-reviewed research report. It does not establish that formalizing proofs of this kind is faster than writing informal proofs, nor does it report a benchmark, a software deployment or a measured reduction in defects. The source material also does not specify the Lean version, the exact Mathlib revision, or whether the complete formalization is available as a separate repository. Those details would matter to readers seeking to reproduce the proof exactly.

The mathematical result is the claim being formalized, while the post explains the author’s proof and its structure. This account alone does not provide independent confirmation of the code or describe any external review. Readers should distinguish the formal proof’s intended conclusion from broader claims about formal methods’ effects on software engineering.

Following the Proof Step by Step

The next step for readers is to consult Biro’s full post, which is organized around the specification, implementation and proof rather than stopping at the automaton’s design. Its listed sections indicate that the core technical work lies in proving the run invariant, handling the initial and inductive cases, and showing how acceptance leads to regularity.

No follow-up release, review or new milestone is identified in the supplied source. The immediate open question for readers interested in reproduction is whether the post links to the complete Lean files and pins the software versions needed to check them. Until those details are confirmed, the article is best treated as a guided explanation of one formalization, not as a reproducibility report.

Key Questions

What does the Lean proof show?

It formalizes a proof that the language of three-row bit strings in which the bottom row is the sum of the top two is regular.

Why does the problem use reversed strings?

Binary addition proceeds from the least significant bit, while the input columns are read in sequence in the other direction. The textbook exercise suggests proving regularity for the reversed language first.

What background does the author expect?

Biro says readers should know a modern statically typed programming language, binary arithmetic, basic propositional logic and inductive proofs.

Does the post show that Lean makes proofs faster?

No. The supplied source presents a worked formalization and discusses what it takes to complete it; it gives no timing comparison or other measurement of proof-writing speed.

Source: hn