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 #
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
A language recognized by a member of V is a language of V, since its syntactic monoid
divides the recognizer.
The languages of V are those recognized by a member of V.
The languages of the pseudovariety of all finite monoids are the regular languages.
The languages of the trivial pseudovariety are the empty and the full language.
The languages of V are closed under inverse images of homomorphisms of free monoids.
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.
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
Equations
- One or more equations did not get rendered due to their size.
Equations
- Monoid.LanguageVariety.instPartialOrder = PartialOrder.lift DFunLike.coe Monoid.LanguageVariety.instPartialOrder._proof_1
The languages of a pseudovariety form a variety of languages.
Equations
- V.toLanguageVariety = { lang := V.languages, isRegular := ⋯, comap_mem := ⋯, leftQuotient_mem := ⋯, rightQuotient_mem := ⋯ }
Instances For
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
A language recognized by a member of V is a language of V.
The languages of V are those recognized by a member of V.
Whether a language of V contains the empty word is invisible to V.
The languages of V are closed under inverse images of homomorphisms of free semigroups.