We know $L^+=L^\star\backslash\{\epsilon\}$. How do we interpret that $\{\epsilon\}^+=\{\epsilon\}$?

  • 1
    $\begingroup$ "We know that $L^+ = L^*\setminus\{\varepsilon\}$." No we don't. $\endgroup$ – David Richerby Apr 8 '17 at 23:14
  • $\begingroup$ @DavidRicherby I meant when $\epsilon\notin L$ and $L$ is an alphabet set $\endgroup$ – 1.. Apr 9 '17 at 20:28
  • $\begingroup$ Then I suggest you edit your question to make it clearer. If you write $L$, everybody is going to assume you're talking about a language, not an alphabet. And when you write $\{\epsilon\}^+$, you are talking about applying $(\cdot)^+$ to a language, rather than the alphabet consisting of just the symbol $\epsilon", right? $\endgroup$ – David Richerby Apr 9 '17 at 20:51

Your first definition only holds if $\epsilon \notin L$.

The Kleene star and plus are defined using recursive sets $V_i$. We have:

$$V_0 = \{\epsilon\}$$ $$V_1 = L$$ $$V_{i+1} = \{ vw : v \in V_i \wedge w \in L\}$$


$$L^* = \bigcup\limits_{i=0}^{\infty} V_i$$ $$L^+ = \bigcup\limits_{i=1}^{\infty} V_i$$

Note that $L^+$ omits $V_0 = \{\epsilon\}$, but does not subtract $\epsilon$ from $L$.

| cite | improve this answer | |

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.