dfa_box_prod
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 }⟩