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

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

| cite | improve this answer | |
  • 2
    $\begingroup$ 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... :) $\endgroup$ – Shaull Feb 3 '14 at 14:47
  • $\begingroup$ 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. $\endgroup$ – FrankW Feb 3 '14 at 15:01
  • $\begingroup$ I guess I can stop my script now! :> @Shaull maybe you can give a hint that focuses their attention? $\endgroup$ – Raphael Feb 3 '14 at 15:59
  • 1
    $\begingroup$ @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. $\endgroup$ – Shaull Feb 3 '14 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.