1
$\begingroup$

In a homework assignment, it's asked

For any alphabet $\Sigma$; for all languages $L$, $M$ on $\Sigma$
Prove that $\forall n>1$, $L^n=M^n\nRightarrow L=M$

The student and I tried in vain to make a proof for $n=2$ by exhibiting distinct $L$ and $M$ with $L^2=M^2$; so much that I now think the statement may be wrong. What are your thoughts?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

What about $\Sigma^*$ and $\Sigma^*\setminus\{11\}$?

Improve this answer
$\endgroup$
1
  • $\begingroup$ That's marvelous, it works! $\endgroup$
    – fgrieu
    Sep 21, 2021 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.