2
$\begingroup$

enter image description here

I can't understand this demonstration. Why if ${w'}_1$ is different from ´${w'}_2$ then we have that $f(u)$ and $v'$ are powers of some string $z$?

$\endgroup$
1
$\begingroup$

The way induction is used is not described in much detail. I try to understand and explain it. The base case where $|f(u)|+|f(v)| = 0$ is not even mentioned.

For the induction step, instead of the alphabet $\{u,v\}$ the alphabet $\{u,v'\}$ is used, supposedly with the map $f'(u) = f(u); f'(v') = v'$. Since $f(u)v' = f(v)$ by the definition of $v'$, $|f'(u)| + |f'(v')| = |f(v)|$. Unless $f(u)$ is empty, $|f'(u)| + |f'(v')| < |f(u)|+|f(v)|$ and therefore the induction hypothesis applies to $f(u)$ and $v'$. If $f(u)$ is empty it is a common power of any string.

$\endgroup$

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.