HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

How is $L^* - \{\epsilon \} \neq L^+$?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
neqepsilonhow

Problem

I was asked which among the following is true:



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



  • $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?

Solution

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.

Context

StackExchange Computer Science Q#101844, answer score: 3

Revisions (0)

No revisions yet.