If $\omega^i = \omega$ then $\omega = \epsilon$

86 Views Asked by At

Prove that If $\omega^i = \omega$ then $\omega = \epsilon$, for every i , $i$ is an integer $\ge 0$ , $\epsilon$ is an empty string and $\omega$ is a word over some alphabet.

I have trouble thinking about ideas regarding this proof. My intuition tells me to prove this by contradiction. Suppose $\omega^i = \omega$ and $\omega \neq \epsilon$. Therefore, $|\omega| \gt 0$.

How can I go about continuing this proof ?

1

There are 1 best solutions below

1
On BEST ANSWER

Letting w = length $\omega$, by hypothesis iw = w.
If i > 1, then w = 0.
If i = 1, then w can be any natural number.
If i = 0, then w = 0.

Thus if i /= 1, $\omega = \epsilon.$