dfa_parallel_prod
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 }