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 #
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
- Language.stringMap φ = Language.equivSetSemiring.symm.toRingHom.comp ((SetSemiring.imageHom φ).comp Language.equivSetSemiring.toRingHom)
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 α)