AFTD Auto-Formalizing Theoretical Domains

dfa_prod

def

The direct product dfa_prod A₁ A₂ of two deterministic finite automata A₁ : DFA α σ₁ and A₂ : DFA α σ₂ over alphabet α is the DFA with state type σ₁ × σ₂, start state (A₁.start, A₂.start), transition function step (q₁, q₂) a = (A₁.step q₁ a, A₂.step q₂ a), and accepting states {p : σ₁ × σ₂ | p.1 ∈ A₁.accept ∧ p.2 ∈ A₂.accept}.

Statement

def dfa_prod {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) : DFA α (σ₁ × σ₂)
Defined in
arXiv:2611.09136 Section 2
Verified
09 Nov 2026
Axioms
none listed
Used by 18

Read back from the Lean

Definition of the product DFA dfa_prod A₁ A₂ for two DFAs A₁ : DFA α σ₁ and A₂ : DFA α σ₂ over the same alphabet type α: it is the DFA with state type σ₁ × σ₂ whose transition function maps ((q₁, q₂), a) to (A₁.step q₁ a, A₂.step q₂ a), whose start state is (A₁.start, A₂.start), and whose set of accepting states is { p : σ₁ × σ₂ | p.1 ∈ A₁.accept ∧ p.2 ∈ A₂.accept }.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The direct product of two DFAs over the same alphabet. -/
def dfa_prod {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) : DFA α (σ₁ × σ₂) where
  step := fun (q₁, q₂) a => (A₁.step q₁ a, A₂.step q₂ a)
  start := (A₁.start, A₂.start)
  accept := { p | p.1 ∈ A₁.accept ∧ p.2 ∈ A₂.accept }
See it in the graphDiscuss this resultChallenge it