Let $L\subseteq \Sigma^*$ such that $\{\epsilon\}\not\in L$. Then for any $S\subseteq \Sigma^*, S=SL\implies S=\emptyset$.

So we suppose $S=SL$ and $S\ne\emptyset$. Then $\exists w\in S$ such that $0\le|w|\le |v|$ for some $v\in S$. Now $|w|\ne 0$, since $|w|=0\implies\{\epsilon\}=w\in S=SL\implies \{\epsilon\}=xy$ for some $x\in S$ and $y\in L\implies x=y=\{\epsilon\}\in L$ which contradicts that $\{\epsilon\}\not\in L$.
Thus $w\ne\{\epsilon\}$ and $\{\epsilon\}\not\in S$. So we have
\begin{align} w \in S &\implies w\in SL\\ &\implies w=sl\;\text{for some}\; s\in S\; \text{and}\; l\in L\\ &\implies |w|=|s|+|l| \end{align}
Here I'm stuck now. I think if I can show that $|l|=0$, then we can arrive at a contradiction.

Your help is highly appreciated.


You should consider (one of) the word $w$ of minimal length in $S$, and show that for this word in particular, you can reach the conclusion that $|l| = 0$.

  • $\begingroup$ So taking $|w|=1$, I can say that either $|s|=0$ or $|l|=0$. But $|s|=0$ is impossible, since $\{\epsilon\}\not\in S$ and hence $|l|=0$, a contradiction. Am I going right? But there is no guarantee that $|w|=1$. $\endgroup$ – Manjoy Das May 26 at 20:49
  • $\begingroup$ No need to do so much cases. Take $|w| = \min\{|u|, u\in S\}$. Then $w = sl$, but $s\in S$, so $|s| \geq |w|$, but we also have $|s| \leq |w|$ (since $w = sl$). $\endgroup$ – Nathaniel May 26 at 21:10
  • $\begingroup$ This leads to $|l|=1$. I am not getting $|l|=0$. $\endgroup$ – Manjoy Das May 26 at 21:13
  • $\begingroup$ No no, this leads to $|l| = 0$, since $|w| = |s|$. $\endgroup$ – Nathaniel May 26 at 21:15
  • $\begingroup$ ahh, my bad... I'm thinking of concatenations. Thanks!! $\endgroup$ – Manjoy Das May 26 at 21:17

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.