Prove/Disprove: $vwvw=vvww$ iff $\{v\}^*\{w\}^*=\{vw\}^*$

Question

Let $\Sigma$ be an alphabet and $v,w\in \Sigma^*$.

I'm trying to prove that: $$vwvw=vvww\quad\text{iff}\quad\{v\}^*\{w\}^*=\{vw\}^*.$$

I tried to do it by induction, with no success. Any help will be greatly appreciated.

Answer 1

Let us assume (Edit: assumption is false) that by $\{vw\}^*$ you actually meant $\{v,w\}^*$.

For, otherwise the result is false. Consider e.g. $vww \in \{v\}^*\{w\}^*$ for $v,w$ nonempty. Then since $w$ is nonempty, it's not equal to $vw$, and since $v$ is nonempty, it's not equal to $vwvw$. Larger strings are obviously ruled out.

---

The proof for $\{v,w\}^*$:

Now if $\{v\}^*\{w\}^* = \{v,w\}^*$, then it must be that $vwvw = v^nw^m$ for $n,m \ge 0$.

The $n=m=2$ case would give $vvww=vwvw$ as desired. The $(n,m) =(1,3),(3,1),(4,0),(0,4)$ cases allow you to prove $v = w$, so in particular $vvww=vwvw$ as well.

The remaining cases $(n,m) = (2,0),(0,2),(1,2),(2,1)$ will prove $w = \varepsilon$ or $v = \varepsilon$.

(This argument can be simplified by applying it to $wv$ in place of $vwvw$.)

---

Suppose now that $vvww = vwvw$. We infer $vw=wv$. Thus a string in $\{v,w\}^*$ is uniquely determined by the number of $v$s and $w$s (although not conversely, e.g. if $v = ww$ then $vww = vv = wwww$). It is therefore clear that each string in $\{v,w\}^*$ can be written by starting with $v$s, followed by $w$s. That is, by an element of $\{v\}^*\{w\}^*$.