Documentation

Linglib.Core.Computability.Variety.Basic

Varieties of languages #

A variety of languages assigns to each alphabet a Boolean algebra of regular languages, closed under quotients by words and under inverse images of homomorphisms of free monoids. The languages of a pseudovariety V of finite monoids over α are those whose syntactic monoid lies in V, equivalently those recognized by a member of V, and they form a variety of languages. The pseudovariety of all finite monoids gives the regular languages, and the trivial one only the empty and the full language. A pseudovariety of finite semigroups gives in the same way, through the syntactic semigroup, Eilenberg's languages of nonempty words.

Implementation notes #

A language of nonempty words is represented by any language with the same nonempty words, since the syntactic semigroup does not see the empty word. A free semigroup has no erasing homomorphisms, so the semigroup side is closed only under inverse images of homomorphisms between free semigroups.

References #

def Monoid.Pseudovariety.languages (V : Pseudovariety) (α : Type u) :
BooleanSubalgebra (Language α)

The languages of a pseudovariety V over α are those whose syntactic monoid lies in V. They form a Boolean subalgebra of Language α.

Equations
  • V.languages α = { carrier := {L : Language α | V.mem L.SyntacticMonoid}, supClosed' := ⋯, infClosed' := ⋯, compl_mem' := ⋯, bot_mem' := ⋯ }
Instances For
    @[simp]
    theorem Monoid.Pseudovariety.mem_languages {V : Pseudovariety} {α : Type u} {L : Language α} :
    L ∈ V.languages α ↔ V.mem L.SyntacticMonoid
    theorem Monoid.Pseudovariety.isRegular_of_mem_languages {V : Pseudovariety} {α : Type u} {L : Language α} (h : L ∈ V.languages α) :
    L.IsRegular
    theorem Monoid.Pseudovariety.mem_languages_of_recognizes {V : Pseudovariety} {α : Type u} {L : Language α} {N : Type u} [Monoid N] (hN : V.mem N) {η : FreeMonoid α →* N} (h : Language.Recognizes η L) :
    L ∈ V.languages α

    A language recognized by a member of V is a language of V, since its syntactic monoid divides the recognizer.

    theorem Monoid.Pseudovariety.mem_languages_iff_exists_recognizes {V : Pseudovariety} {α : Type u} {L : Language α} :
    L ∈ V.languages α ↔ ∃ (N : Type u) (x : Monoid N) (η : FreeMonoid α →* N), V.mem N ∧ Language.Recognizes η L

    The languages of V are those recognized by a member of V.

    @[simp]
    theorem Monoid.Pseudovariety.mem_languages_top {α : Type u} {L : Language α} :
    L ∈ ⊤.languages α ↔ L.IsRegular

    The languages of the pseudovariety of all finite monoids are the regular languages.

    @[simp]
    theorem Monoid.Pseudovariety.languages_bot {α : Type u} :
    ⊥.languages α = ⊥

    The languages of the trivial pseudovariety are the empty and the full language.

    theorem Monoid.Pseudovariety.comap_mem_languages {V : Pseudovariety} {α β : Type u} {L : Language β} (h : L ∈ V.languages β) (φ : FreeMonoid α →* FreeMonoid β) :
    {w : List α | φ (FreeMonoid.ofList w) ∈ L} ∈ V.languages α

    The languages of V are closed under inverse images of homomorphisms of free monoids.

    theorem Monoid.Pseudovariety.leftQuotient_mem_languages {V : Pseudovariety} {α : Type u} {L : Language α} (h : L ∈ V.languages α) (u : List α) :
    L.leftQuotient u ∈ V.languages α
    theorem Monoid.Pseudovariety.rightQuotient_mem_languages {V : Pseudovariety} {α : Type u} {L : Language α} (h : L ∈ V.languages α) (u : List α) :
    structure Monoid.LanguageVariety :
    Type (u + 1)

    A variety of languages assigns to each alphabet a Boolean algebra of regular languages, closed under inverse images of homomorphisms between free monoids and under left and right quotients by words.

    • lang (α : Type u) : BooleanSubalgebra (Language α)

      The languages of the variety over each alphabet.

    • isRegular {α : Type u} {L : Language α} : L ∈ self.lang α → L.IsRegular

      Every member is regular.

    • comap_mem {α β : Type u} {L : Language β} (φ : FreeMonoid α →* FreeMonoid β) : L ∈ self.lang β → {w : List α | φ (FreeMonoid.ofList w) ∈ L} ∈ self.lang α

      The inverse image of a member under a homomorphism of free monoids is a member.

    • leftQuotient_mem {α : Type u} {L : Language α} (u : List α) : L ∈ self.lang α → L.leftQuotient u ∈ self.lang α

      The left quotient of a member by a word is a member.

    • rightQuotient_mem {α : Type u} {L : Language α} (u : List α) : L ∈ self.lang α → L.rightQuotient u ∈ self.lang α

      The right quotient of a member by a word is a member.

    Instances For
      @[instance_reducible]
      instance Monoid.LanguageVariety.instDFunLikeTypeBooleanSubalgebraLanguage :
      DFunLike LanguageVariety (Type u) fun (α : Type u) => BooleanSubalgebra (Language α)
      Equations
      • One or more equations did not get rendered due to their size.
      theorem Monoid.LanguageVariety.ext {𝒱 𝒲 : LanguageVariety} (h : ∀ (α : Type u) (L : Language α), L ∈ 𝒱 α ↔ L ∈ 𝒲 α) :
      𝒱 = 𝒲
      theorem Monoid.LanguageVariety.ext_iff {𝒱 𝒲 : LanguageVariety} :
      𝒱 = 𝒲 ↔ ∀ (α : Type u) (L : Language α), L ∈ 𝒱 α ↔ L ∈ 𝒲 α
      theorem Monoid.LanguageVariety.le_def {𝒱 𝒲 : LanguageVariety} :
      𝒱 ≤ 𝒲 ↔ ∀ (α : Type u) ⦃L : Language α⦄, L ∈ 𝒱 α → L ∈ 𝒲 α

      The languages of a pseudovariety form a variety of languages.

      Equations
      Instances For
        def Semigroup.Pseudovariety.languages (V : Pseudovariety) (α : Type u) :
        BooleanSubalgebra (Language α)

        The languages of a pseudovariety V of finite semigroups over α are those whose syntactic semigroup lies in V. They form a Boolean subalgebra of Language α.

        Equations
        • V.languages α = { carrier := {L : Language α | V.mem L.SyntacticSemigroup}, supClosed' := ⋯, infClosed' := ⋯, compl_mem' := ⋯, bot_mem' := ⋯ }
        Instances For
          @[simp]
          theorem Semigroup.Pseudovariety.mem_languages {V : Pseudovariety} {α : Type u} {L : Language α} :
          L ∈ V.languages α ↔ V.mem L.SyntacticSemigroup
          theorem Semigroup.Pseudovariety.isRegular_of_mem_languages {V : Pseudovariety} {α : Type u} {L : Language α} (h : L ∈ V.languages α) :
          L.IsRegular
          theorem Semigroup.Pseudovariety.mem_languages_of_recognizes {V : Pseudovariety} {α : Type u} {L : Language α} {T : Type u} [Semigroup T] (hT : V.mem T) {η : FreeSemigroup α →ₙ* T} (h : Language.RecognizesSemigroup η L) :
          L ∈ V.languages α

          A language recognized by a member of V is a language of V.

          theorem Semigroup.Pseudovariety.mem_languages_iff_exists_recognizes {V : Pseudovariety} {α : Type u} {L : Language α} :
          L ∈ V.languages α ↔ ∃ (T : Type u) (x : Semigroup T) (η : FreeSemigroup α →ₙ* T), V.mem T ∧ Language.RecognizesSemigroup η L

          The languages of V are those recognized by a member of V.

          @[simp]
          theorem Semigroup.Pseudovariety.insert_nil_mem_languages_iff {V : Pseudovariety} {α : Type u} {L : Language α} :
          insert [] L ∈ V.languages α ↔ L ∈ V.languages α

          Whether a language of V contains the empty word is invisible to V.

          theorem Semigroup.Pseudovariety.comap_mem_languages {V : Pseudovariety} {α β : Type u} {L : Language β} (h : L ∈ V.languages β) (φ : FreeSemigroup α →ₙ* FreeSemigroup β) :
          {w : List α | ∃ (u : FreeSemigroup α), FreeMonoid.toList (FreeSemigroup.toFreeMonoid u) = w ∧ FreeMonoid.toList (FreeSemigroup.toFreeMonoid (φ u)) ∈ L} ∈ V.languages α

          The languages of V are closed under inverse images of homomorphisms of free semigroups.

          theorem Semigroup.Pseudovariety.leftQuotient_mem_languages {V : Pseudovariety} {α : Type u} {L : Language α} (h : L ∈ V.languages α) (u : List α) :
          L.leftQuotient u ∈ V.languages α
          theorem Semigroup.Pseudovariety.rightQuotient_mem_languages {V : Pseudovariety} {α : Type u} {L : Language α} (h : L ∈ V.languages α) (u : List α) :