# 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$.

• Not sure if that helps, but $g(A,B) = \bigcup_{\sigma \in \Sigma} (A / \{\sigma\}) \cdot \sigma \cdot (B \backslash \{\sigma\})$. – Raphael Feb 2 '14 at 14:13
• For $A=B=\Sigma^+$, we have $A \cdot B = \Sigma^{\geq 2} \subsetneq \Sigma^+ = g(A,B)$, but both are of course infinite. – Raphael Feb 2 '14 at 15:05
• @Raphael - Yes, clearly a counterexample (if it exists) won't come from infinite languages. But it's still a nice example. – Shaull Feb 2 '14 at 15:26

For $A = \{a, aaba\}$ and $B = \{a, abaa\}$ we find
$|g(A,B) = \{a, abaa, aaba, aababaa\}| = 4 > 3 = |\{aa, aabaa, aabaabaa\}| = |A\cdot B|$.