Documentation

Linglib.Core.Computability.Language

Languages as sets of words, and string homomorphisms #

Mirror of Mathlib/Computability/Language.lean. A language over α is a subset of the free monoid on α, added by union and multiplied by concatenation, so Language α is SetSemiring (FreeMonoid α). A string homomorphism φ : FreeMonoid α →* FreeMonoid β then acts on languages by SetSemiring.imageHom φ read through that identification. It inherits the functor laws of imageHom, and on a map of letters it is Language.map. [UPSTREAM]

References #

@[simp]
theorem Language.mem_singleton_iff {α : Type u_1} {x y : List α} :
x ∈ {y} ↔ x = y
def Language.equivSetSemiring {α : Type u_1} :
Language α ≃+* SetSemiring (FreeMonoid α)

A language over α is a subset of the free monoid on α, with union as addition and concatenation as multiplication.

Equations
  • One or more equations did not get rendered due to their size.
Instances For
    noncomputable def Language.stringMap {α : Type u_1} {β : Type u_2} (φ : FreeMonoid α →* FreeMonoid β) :
    Language α →+* Language β

    The image of a language under a string homomorphism φ: SetSemiring.imageHom φ read through Language.equivSetSemiring.

    Equations
    Instances For
      @[simp]
      theorem Language.mem_stringMap {α : Type u_1} {β : Type u_2} {φ : FreeMonoid α →* FreeMonoid β} {L : Language α} {w : List β} :
      w ∈ (stringMap φ) L ↔ ∃ v ∈ L, FreeMonoid.toList (φ (FreeMonoid.ofList v)) = w
      @[simp]
      theorem Language.stringMap_id {α : Type u_1} :
      stringMap (MonoidHom.id (FreeMonoid α)) = RingHom.id (Language α)
      theorem Language.stringMap_comp {α : Type u_1} {β : Type u_2} {γ : Type u_3} (ψ : FreeMonoid β →* FreeMonoid γ) (φ : FreeMonoid α →* FreeMonoid β) :
      stringMap (ψ.comp φ) = (stringMap ψ).comp (stringMap φ)
      @[simp]
      theorem Language.stringMap_map {α : Type u_1} {β : Type u_2} (f : α → β) :
      stringMap (FreeMonoid.map f) = map f

      On a map of letters, stringMap is Language.map.