Find all strings of $w$ that satisfy following equation

62 Views Asked by At

Solve the following string equation on the alphabet $A = \{1, 0\}$ and find all $w$'s:

$w011 = 011w$

1

There are 1 best solutions below

0
On
$w_0$ $w_1$ $w_2$ $w_3$ $w_4$ ... $w_{n-2}$ $w_{n-1}$ $w_{n}$ 0 1 1
0 1 1 $w_0$ $w_1$ ... $w_{n-5}$ $w_{n-4}$ $w_{n-3}$ $w_{n-2}$ $w_{n-1}$ $w_{n}$

We can see that $w_0$ has to be equal to $w_3$, $w_6$... Recursively $n-2$ has to be divisible by 3, because only $w_0 = 0$ from set {$w_0$, $w_1$, $w_2$}. So all strings are of form $(011)*$.

So we have $w=\emptyset$, $w = 011$, $w=011011$...