3
$\begingroup$

I was asked which among the following is true:

  1. $\Sigma^*-\{\epsilon\} = \Sigma^+$
  2. $L^* - \{\epsilon \} = L^+$

As I can see, both $\Sigma^*$ & $L^*$ are sets. I thought both were true because of set difference, but the answer lists only the first option as correct and the second as false. How so?

$\endgroup$
3
$\begingroup$

If $\varepsilon \in L$, then necessarily $\varepsilon \in L^+$ (and the converse as well). This is because $L$ itself is contained in $L^+$ and $L^+$ is defined as the union over the powers $L^i$ of $L$ for $i \in \mathbb{N}_+$. Note $L^+$ is not defined as $L^\ast \setminus \{ \varepsilon \}$; this is a common mistake.

Hence, $\varepsilon \not\in L^+$ holds if and only if $\varepsilon \not\in L$. This is the case for the alphabet $\Sigma$, hence why it is correct in the first case.

$\endgroup$
  • $\begingroup$ Can't $\sum = \{\epsilon\}$ or $\epsilon \in \sum$? $\endgroup$ – Mr. Sigma. Dec 20 '18 at 13:17
  • 1
    $\begingroup$ @Mr.Sigma. Well, it depends on what $\Sigma$ is. Usually it is meant as an alphabet, so defining it like that would mean $\varepsilon$ is a symbol; I have no clue how you would separate that from the empty word $\varepsilon$ (though I could imagine Machiavellian examiners abusing such things). If $\Sigma$ is meant as a language, then, sure, $\Sigma = \{ \varepsilon \}$ is possible (and not ambiguous). Note $\Sigma$ cannot be just a "set" since it must contain words; otherwise, the definition for $\Sigma^+$ simply does not work because $\Sigma^i$ is undefined (regarding concatenation). $\endgroup$ – dkaeae Dec 20 '18 at 13:20
  • $\begingroup$ oh, so should I assume null is not to be taken as an alphabet unless mentioned? $\endgroup$ – Mr. Sigma. Dec 20 '18 at 13:23
  • 1
    $\begingroup$ @Mr.Sigma. With "null" you mean the empty word $\varepsilon$? As I have said, I cannot imagine using $\varepsilon$ being used as a symbol except in the (very) restricted case of formulating trick questions. At any rate, $\Sigma$ should be given explicitly; if this is not the case, then $\varepsilon$ can safely be assumed not to be an element of it (since words should not be elements of alphabets, which are sets of symbols). $\endgroup$ – dkaeae Dec 20 '18 at 13:44
  • 4
    $\begingroup$ 2. really doesn't have a yes/no answer because $L$ isn't specified, but what probably is meant there is whether $\forall L: L^* - \{\epsilon \} = L^+$, in which case the answer is no, as dkaeae explains. $\endgroup$ – reinierpost Dec 20 '18 at 14:40

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.