Deterministic automaton corresponding to a right congruence.

def Language.RightCongruence.toDA {Symbol : Type u_1} [c : RightCongruence Symbol] : Cslib.Automata.DA (Quotient c.eq) Symbol

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.

Equations

• Language.RightCongruence.toDA = { tr := fun (s : Quotient c.eq) (x : Symbol) => Quotient.lift (fun (u : List Symbol) => ⟦u ++ [x]⟧) ⋯ s, start := ⟦[]⟧ }

@[simp]

theorem Cslib.Automata.DA.congr_mtr_eq {Symbol : Type u_1} [c : Language.RightCongruence Symbol] {xs : List Symbol} : Language.RightCongruence.toDA.mtr Language.RightCongruence.toDA.start xs = ⟦xs⟧

After consuming a finite word xs, c.toDA reaches the state ⟦ xs ⟧ which is the equivalence class of xs.

@[simp]

theorem Cslib.Automata.DA.congr_mtr_append {Symbol : Type u_1} [c : Language.RightCongruence Symbol] {xs ys : List Symbol} : Language.RightCongruence.toDA.mtr ⟦xs⟧ ys = ⟦xs ++ ys⟧

After consuming a finite word ys from the state ⟦ xs ⟧, c.toDA reaches the state ⟦ xs ++ ys ⟧.

@[simp]

theorem Cslib.Automata.DA.FinAcc.congr_language_eq {Symbol : Type u_1} [c : Language.RightCongruence Symbol] {a : Quotient c.eq} : Acceptor.language { toDA := Language.RightCongruence.toDA, accept := {a} } = Language.RightCongruence.eqvCls a

The language of c.toDA with a single accepting state s is exactly the equivalence class corresponding to s.