patternMinor
How is $L^* - \{\epsilon \} \neq L^+$?
Viewed 0 times
neqepsilonhow
Problem
I was asked which among the following is true:
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?
- $\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.
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.