AFTD Auto-Formalizing Theoretical Domains

Cslib.RightCongruence.toDA

defimported Lean

Every right congruence gives rise to a DA whose states are the equivalence classes of the right congruence, whose start state is the empty word, and whose transition functiuon is concatenation on the right of the input symbol. Note that the transition function is well-defined only because c is a right congruence.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
variable {Symbol : Type*} in
@[scoped grind =]
def Cslib.RightCongruence.toDA [c : RightCongruence Symbol] : Automata.DA (Quotient c.eq) Symbol
Defined in
CSLib, `Cslib.RightCongruence.toDA`
Lean proof
By Ching-Tsun Chou, from github.com/leanprover/cslib at 3951377e5a3f (Copyright (c) 2026 Ching-Tsun Chou. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.
Verified
08 Oct 2026
Axioms
none listed
Built on 3
  • Cslib.Automata.DAA deterministic automaton extends a FLTS with a unique initial state.
  • Cslib.RightCongruenceA right congruence is an equivalence relation on finite sequences (represented by lists) that is preserved by concatenation on the right.…
  • Cslib.FLTSA Functional Labelled Transition System (FLTS) for a type of states (State) and a type of transition labels (Label) consists of a…

Lean source view module on GitHub

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
variable {Symbol : Type*} in
/-- Every right congruence gives rise to a DA whose states are the equivalence classes of the right congruence, whose start state is the empty word, and whose transition functiuon is concatenation on the right of the input symbol. Note that the transition function is well-defined only because `c` is a right congruence. -/
@[scoped grind =]
def Cslib.RightCongruence.toDA [c : RightCongruence Symbol] : Automata.DA (Quotient c.eq) Symbol where
  tr s x := Quotient.lift (fun u ↦ ⟦ u ++ [x] ⟧) (by
    intro u v h_eq
    apply Quotient.sound
    exact right_cov.elim [x] h_eq
  ) s
  start := ⟦ [] ⟧
See it in the graphDiscuss this resultChallenge it