patternMinor
Glue-concatenation v.s concatenation
Viewed 0 times
concatenationgluestackoverflow
Problem
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$.
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$.
Solution
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.
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.
Context
StackExchange Computer Science Q#20212, answer score: 3
Revisions (0)
No revisions yet.