1

Given the words $v,w \in \sum^*$, is this correct?

  1. If $v^6w^8 = w^{12}v^4$ then $(vw)^2 = v^2w^2$

  2. If $vw^2 = wv^2$ then $v=w$

For one, I tried $v=\epsilon, w=\epsilon$ and it worked, and I also tried $v=aa, w= aaaa$ and it also worked, but I am not quite sure how to prove it.

Regarding two, I could not come up with examples except $v,w=\epsilon$.

Any help is appreciated.

Community
  • 1
TheNotMe
  • 4,841

2 Answers2

2

In case $1$, taking lengths you have

$$ 6{\sf length}(v)+8{\sf length}(w)=12{\sf length}(w)+4{\sf length}(v) $$

so ${\sf length}(v)=2{\sf length}(w)$. So looking at the $12{\sf length}(w)$ leftmost charcaters in the word $v^6w^8=w^{12}v^4$, we see that $v^6=w^{12}$, so $v=w^2$.

Similarly in case $2$, loking at lengths you see that $v$ and $w$ have the same length, and looking at the ${\sf length}(v)$ leftmost charcaters in the word $vw^2=wv^2$ you see that $v=w$.

Ewan Delanoy
  • 61,600
  • "So looking at the..." what did you mean by that? how did you get from $|v| = 2|w|$ to $v=w^2$? – TheNotMe Oct 27 '13 at 16:20
  • I mean what it means : look at the first character, then the second, etc, do this $12|w|$ times, and then look at the word formed by all those characters. Since the big word is $v^6w^8$, this prefix is $v^6$. But since the big word is also $w^{12}v^4$, this prefix is also $w^{12}$. – Ewan Delanoy Oct 27 '13 at 16:21
  • What bothers me is that the length of $w$ is double the length of $v$, but that doesn't necessarily mean that they have same characters also. (Sorry, I'm a newbie in automata) – TheNotMe Oct 27 '13 at 16:22
  • Not necessarily, indeed, but this was not the argument I used. Please re-read my comment above – Ewan Delanoy Oct 27 '13 at 16:24
  • Oh, I see. And in this case, $(vw)^2 = (w^3)^2 = w^6 = v^2w^2 = w^4w^2 = w^6$ which means its correct? – TheNotMe Oct 27 '13 at 17:10
1

The answer is yes in both cases. You could use Corollary 1.2.6 of Lothaire's book Combinatorics on Words, which says:

If you have a nontrivial relation between two words $v$ and $w$, then both words are powers of the same word $u$.

Thus $v = u^a$ and $w = v^b$ for some positive integers $a$ and $b$ and your questions become trivial.

Mikasa
  • 67,374
J.-E. Pin
  • 40,163