AFTD Auto-Formalizing Theoretical Domains

dfa_parallel_prod

def

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

Statement

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

Read back from the Lean

The definition dfa_parallel_prod takes types α₁, α₂, σ₁, and σ₂, and two deterministic finite automata A₁ : DFA α₁ σ₁ and A₂ : DFA α₂ σ₂, and constructs a new automaton of type DFA (α₁ × α₂) (σ₁ × σ₂) whose: - start state is (A₁.start, A₂.start); - transition function step takes a state (q₁, q₂) : σ₁ × σ₂ and an input pair (a₁, a₂) : α₁ × α₂ to (A₁.step q₁ a₁, A₂.step q₂ a₂); - accept set consists of all pairs p : σ₁ × σ₂ such that p.1 ∈ A₁.accept and p.2 ∈ A₂.accept (the Cartesian product of the two accept sets).

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

/-- Parallel two-tape product of two deterministic finite automata. -/
def dfa_parallel_prod {α₁ α₂ σ₁ σ₂ : Type*} (A₁ : DFA α₁ σ₁) (A₂ : DFA α₂ σ₂) : DFA (α₁ × α₂) (σ₁ × σ₂) where
  step := fun (q₁, q₂) (a₁, 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