nfa_isomorphic_up_to_perm
Two NFAs M₁ and M₂ over alphabet α with state sets σ₁ and σ₂ are isomorphic up to state bijection and alphabet permutation if there exist a state bijection e : σ₁ ≃ σ₂ and a permutation π of the alphabet such that e preserves initial states, accepting states, and transitions with respect to π.
Statement
def nfa_isomorphic_up_to_perm {α σ₁ σ₂ : Type*} (M₁ : NFA α σ₁) (M₂ : NFA α σ₂) : Prop
- Related work
- arXiv:2610.08525, Stronger bounds on the degree of ambiguity of finite automata
- Verified
- 29 Oct 2026
- Axioms
- none listed
- Used by 1
- nfa_isomorphic_up_to_perm_reflEvery NFA is isomorphic to itself up to state bijection and alphabet permutation, witnessed by the identity bijection on states and the…
Read back from the Lean
The proposition nfa_isomorphic_up_to_perm M₁ M₂ asserts that there exist a bijection (equivalence) e : σ₁ ≃ σ₂ between the state spaces and a permutation π : Equiv.Perm α of the alphabet α such that:
1. For every state s : σ₁, s is a start state of M₁ if and only if e s is a start state of M₂.
2. For every state s : σ₁, s is an accepting state of M₁ if and only if e s is an accepting state of M₂.
3. For all states s, t : σ₁ and every symbol a : α, t is reachable from s on transition a in M₁ (t ∈ M₁.step s a) if and only if e t is reachable from e s on transition π a in M₂ (e t ∈ M₂.step (e s) (π a)).
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
/-- Two NFAs are isomorphic up to state bijection and alphabet permutation. -/ def nfa_isomorphic_up_to_perm {α σ₁ σ₂ : Type*} (M₁ : NFA α σ₁) (M₂ : NFA α σ₂) : Prop := ∃ (e : σ₁ ≃ σ₂) (π : Equiv.Perm α), (∀ s, s ∈ M₁.start ↔ e s ∈ M₂.start) ∧ (∀ s, s ∈ M₁.accept ↔ e s ∈ M₂.accept) ∧ (∀ s t a, t ∈ M₁.step s a ↔ e t ∈ M₂.step (e s) (π a))