Glue-concatenation v.s concatenation I wanted to give the following as a homework question, but my first few attempts to solve it failed, so now I'm just curios for a solution:

For two words $x,y\in \Sigma^*$ and for a letter $\sigma\in \Sigma$ we define the glue-concatenation of $x\sigma$ and $\sigma y$ to be $g(x\sigma,\sigma y)=x\sigma y$, and for words $w,z$ such that the last letter in $w$ differs from the first letter in $z$, the glue concatenation is undefined.

For languages $A,B\subseteq \Sigma^*$, we lift the glue operator such that $g(A,B)=\{g(w\sigma,\sigma z):w\sigma \in A, \sigma z\in B\}$ (note that we only consider words for which $g$ is defined).


  The question: is it always true that $|g(A,B)|\le |A\cdot B|$?


Observe that trying to prove that if $g(x,y)\neq g(w,z)$ then $xy\neq wz$ will fail, since for example, $g(a,abb)\neq g(aab,b)$, but $a\cdot abb=aab\cdot b$.
The statement does not hold.

For $A = \{a, aaba\}$ and $B = \{a, abaa\}$ we find

$|g(A,B) = \{a, abaa, aaba, aababaa\}| = 4 &gt; 3 = |\{aa, aabaa, aabaabaa\}|  = |A\cdot B|$.

As a sidenote, I'd say this could actually be a worthwile exercise task, once students are reasonably experienced with standard proof techniques. After all, you only really learn how to attack such problems from practising.