1
$\begingroup$

$\Sigma^* - \{\epsilon\} = \Sigma^+$

$L^* - \{\epsilon\} = L^+$

Which of the above is always true?

I was following a discussion on a site and I came across this question. Some fellow scholars claimed that the second statement is not always true. The answer they provided is this:

$S_1$: $Σ^* – \{ϵ\} = Σ^+$: TRUE // Always true, definition of $Σ^+$

$S_2$: $L^* – \{ϵ\} = L^+$: FALSE // May or may not be true

False when $ϵ$ belongs to $L$, then $L^+$ and $L^*$ will both contain $ϵ$.

PS: In $S_2$, it depends purely on the given language.

But I have this doubt:

How can $L^+$ contain $ϵ$? we obtain $L^+$ by deleting $ϵ$ from $L^*$, and in $L^*$ of the language where $L=\{ϵ\}$, $L^*$ will only contain $ϵ$, so if we remove $ϵ$ from it, then the language should become $\emptyset$, which is nothing but $L^+$ here. So shouldn't the second statement also be true?

Say $L^+ = \{ϵ,ϵϵ,ϵϵϵ,\dots\}$.

Now an important point. Note that we say Set of all strings, now in set theory duplicates are not allowed, moreover $ϵ= ϵϵ =ϵϵϵ =\dots$. They are all just the same. So $L^∗$ should be only $\{ϵ\}$, rather than $\{ϵ,ϵ,ϵϵ,ϵϵϵ,\dots\}$, right?

$\endgroup$
  • $\begingroup$ Usual definition is $L^+ = L \cdot L^*$. $\endgroup$ – Dmitri Urbanowicz Aug 30 at 11:28
  • $\begingroup$ see my doubt above $\endgroup$ – HIRAK MONDAL Aug 30 at 12:10
5
$\begingroup$

You got the definition of $L^+$ wrong. It is not $L^* \setminus \{\epsilon\}$. Rather, it is $$ L^+ = \bigcup_{n=1}^* L^n. $$ You can check that $\epsilon \in L^+$ iff $\epsilon \in L$. Therefore:

  • If $\epsilon \notin L$ then $L^+ = L^*\setminus\{\epsilon\}$.
  • If $\epsilon \in L$ then $L^+ = L^*$.
$\endgroup$
  • $\begingroup$ Thank u sir... :) $\endgroup$ – HIRAK MONDAL Aug 30 at 17: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.