# Equations on the free monoid??

While studying a bit of Joachim Lambek's calculus and some other applications of formal languages to the study of the structure of human language, I have come accross a reference to what authors like André Lentin has developed for the study of word combinations, namely, the so-called equations on the free monoid.

Could anyone explain me what those equations on the free monoid are?

Best regards and thanks in advance.

• Formally just a pair of elements, and is said to hold via an interpretation in a monoid if both elements mapped to the same. – Berci Jun 13 '18 at 22:00
• Could you please be more specific? Isnt the term "equations" taken there in its proper sense?? I thought there would be some underlying equations or anything of that sort..... – Javier Arias Jun 13 '18 at 22:07

## 1 Answer

You can find the definition and a presentation of the main results in the Wikipedia entry Équation entre mots which apparently has not been translated in any other language.

Let $A$ be a finite set of constants and let $\Xi$ be a finite set of variables. A word equation is a pair $(u, v)$ of words of $(A \cup \Xi)^*$. A solution is a map $f:\Xi \to A^*$, which extends uniquely to a monoid homomorphism from $(A \cup \Xi)^*$ to $A^*$, such that $f(u) = f(v)$.

Quoting Wikipedia, the map $f(T) = bab$, $f(X) = abb$, $f(Y) = ab$, $f(Z) = ba$ is a solution of the equation $$XaTZaT=YZbXaabY$$ since $(abb)a(bab)(ba)a(bab) = (ab)(ba)b(abb)aab(ab)$.

Makanin's theorem states that deciding whether a given equation has a solution is decidable.

• Well, I guess the next question is. What advantages does the usage of such conceptual machinery and formalism bring? I mean, in which way does the study of grammar and / or formal language benefit from that? – Javier Arias Jun 15 '18 at 17:21
• Do not take it in bad part, but I can hardly answer this further question within a three line comment. – J.-E. Pin Jun 15 '18 at 20:06
• Ok. But you can try to provide an answer pretty along the lines you provided above. Anyway, you are welcome, even if you prefer not to. – Javier Arias Jun 17 '18 at 0:29