Let $\Sigma$ be an alphabet. Have a look at following definitions frequently used in literature containing Kleene star and Kleene plus.

$\Sigma^* := \Sigma^+ \cup \{\varepsilon\}$
$\Sigma^+ := \Sigma^* \setminus \{\varepsilon\}$

These definitions lead to different sets iff $\varepsilon \in \Sigma_i$ for some $i$. What's the proper one in general context? Is it similar to mathematical issues like multiplicative identity in rings or including zero in the set of natural numbers?

| cite | improve this question | | | | |
  • 2
    $\begingroup$ Note that you can't define both of them like that: you need to give a concrete definition of either $\Sigma^+$ or $\Sigma^*$ and then you can define the other one using one of the two equations you give. $\endgroup$ – David Richerby Dec 22 '14 at 17:18
  • $\begingroup$ What makes you think there is a single proper one that is right for all contexts? When you write "What's the proper one in general context?", I think you are starting from some implicit assumptions/premises that are not accurate. So you might benefit from trying to spell out your reasoning and where this question came from and what you are assuming (it will probably help clarify what your misconception is more clearly). $\endgroup$ – D.W. Dec 22 '14 at 22:24
  • 3
    $\begingroup$ The second definition is wrong: $\{\varepsilon\}^+ = \{\varepsilon\}$. In general: $\Sigma^+ = \Sigma\Sigma^* = \Sigma^*\Sigma$. $\endgroup$ – reinierpost Dec 22 '14 at 22:43

$\Sigma$ is a finite set of elements called letters. A word is a sequence of 0 or more letters. For every alphabet, there is a unique 0-letter word called the empty word, denoted $\epsilon$. By definition, $\epsilon\notin \Sigma$, for eny $\Sigma$.

Thus, $\Sigma^*$ and $\Sigma^+$ are both well defined, and are used for different purposes.

Mathematically, $\Sigma^*$ with the concatenation operation is a monoid, with $\epsilon$ being the identity element. $\Sigma^+$ is thus a semi-group, with the concatenation operation, as it doesn't have an identity element.

| 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.