Prove or disprove: there exists two words, $x$ and $y$ in {a, b}*, such that $ax^2b = y^2$.

16 Views Asked by At

I know this is a "disprove" answer, but I'm having trouble formally articulating it. Please help me.

1

There are 1 best solutions below

0
On BEST ANSWER

Suppose such words would exist, then $y$ must be of the form $a w b$ for some word $w \in \{ a, b \}^\ast$ and moreover, $y^2$ can be expressed as $a w b a w b$. As we thus have $a x^2 b = a w b a w b$ it follows that $x^2 = wbaw$. By splitting the latter string into two halves we find $x = wb$ and $x = aw$ which is a contradiction -- these strings cannot have the same number of $a$s and $b$s, respectively and therefore such $x$ and $y$ cannot exist.