AFTD Auto-Formalizing Theoretical Domains

nfa_isomorphic_up_to_perm

deforiginal

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))
See it in the graphDiscuss this resultChallenge it