AFTD Auto-Formalizing Theoretical Domains

dfa_box_prod

def

The sequential two-tape product automaton (box product) of two DFAs A₁ and A₂ with disjoint input alphabets has state type σ₁ × σ₂, input alphabet α₁ ⊕ α₂, start state (A₁.start, A₂.start), accepting states A₁.accept ×ˢ A₂.accept, and transitions δ((q₁, q₂), inl a₁) = (A₁.step q₁ a₁, q₂) and δ((q₁, q₂), inr a₂) = (q₁, A₂.step q₂ a₂).

Statement

def dfa_box_prod {α₁ α₂ σ₁ σ₂ : Type*} (A₁ : DFA α₁ σ₁) (A₂ : DFA α₂ σ₂) :
    DFA (Sum α₁ α₂) (σ₁ × σ₂)
Defined in
arXiv:2611.09136 Section 2
Verified
10 Nov 2026
Axioms
none listed

Read back from the Lean

Given types α₁, α₂, σ₁, and σ₂, and two deterministic finite automata A₁ : DFA α₁ σ₁ and A₂ : DFA α₂ σ₂, dfa_box_prod A₁ A₂ is the deterministic finite automaton with alphabet Sum α₁ α₂ (α₁ ⊕ α₂) and state type σ₁ × σ₂ whose: - transition function maps a state (q₁, q₂) and an input symbol a to: - (A₁.step q₁ a₁, q₂) if a = Sum.inl a₁, - (q₁, A₂.step q₂ a₂) if a = Sum.inr a₂; - start state is (A₁.start, A₂.start); - accepting state set 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 sequential two-tape product automaton (box product) of two DFAs with disjoint input alphabets. -/
def dfa_box_prod {α₁ α₂ σ₁ σ₂ : Type*} (A₁ : DFA α₁ σ₁) (A₂ : DFA α₂ σ₂) :
    DFA (Sum α₁ α₂) (σ₁ × σ₂) :=
  ⟨fun (q₁, q₂) a =>
    match a with
    | Sum.inl a₁ => (A₁.step q₁ a₁, q₂)
    | Sum.inr a₂ => (q₁, A₂.step q₂ a₂),
   (A₁.start, A₂.start),
   { p | p.1 ∈ A₁.accept ∧ p.2 ∈ A₂.accept }⟩
See it in the graphDiscuss this resultChallenge it