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. Feb 2 '14 at 15:26

The statement does not hold.

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

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.

• I thought the example should be simple! Very nice. Thanks! I won't feel right putting this as an exercise after not having solved it myself, but maybe, if I feel extra-cruel... :) Feb 3 '14 at 14:47
• I wouldn't give it as a mandatory exercise, if I know a significant number of the students won't be able to find a solution. But I've given such tasks as voluntary extras to challenge the better students. The feedback was mostly positive. Feb 3 '14 at 15:01
• I guess I can stop my script now! :> @Shaull maybe you can give a hint that focuses their attention?
– Raphael
Feb 3 '14 at 15:59
• @Raphael - When I thought about it, I reached the conclusion that if a counterexample exists, it would be one where all the words in A end with the same letter, and all the words in B begin with this letter. I think that's a useful hint. However, I'm not sure what this question really teaches. It's just a cute nontrivial property... We'll probably end up giving it as a bonus. Feb 3 '14 at 20:24