Kleene star and Kleene plus

Problem Detail: 

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?

Asked By : RomeoAndJuliet

Answered By : Shaull

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35600