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.Cslib.RightCongruence.toDA← Cslib.RightCongruence.toDA (Cslib/Computability/Automata/DA/Congr.lean:27): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 3
- Cslib.Automata.DAA deterministic automaton extends a
FLTSwith 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…
- Cslib.Automata.DAA deterministic automaton extends 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 := ⟦ [] ⟧