Suppose $Σ=\{0,1\}$; then $Σ^*$ is the set of all strings over $Σ$.
Is $Σ^*$ over $Σ$ finte?
$\begingroup$
$\endgroup$
-
1$\begingroup$ did you look at Kleene star to see what $\Sigma^*$ actually means? $\endgroup$ – Ran G. Jun 16 '15 at 22:02
-
$\begingroup$ Yes, I know what it means, but is | Σ* | finite or not ? $\endgroup$ – Mohammed Jun 16 '15 at 22:07
-
$\begingroup$ can you specify some words that belong to $\Sigma^*$? how many of these can you specify (more than 2? more than 3? how about more than 10?) $\endgroup$ – Ran G. Jun 16 '15 at 22:10
-
1$\begingroup$ The answer is: Σ* does not have a length. The reason for it is that Σ* is a set of strings, an infinite set of strings, which are all of finite length. The notation |Σ*| is for the cardinality of Σ*, i.e. its number of elements, which as I said is infinite. $\endgroup$ – babou Jun 16 '15 at 22:18
-
$\begingroup$ Thanks babou. Well, I guess I deserved that one for this (; $\endgroup$ – Ran G. Jun 16 '15 at 22:28
$\begingroup$
$\endgroup$
The star operator is a unary operator known as Kleene star (or Kleene closure) and the result of its application on $\Sigma$ (an arbitrary set of strings) is another set that contains all possible finite strings constructed using only strings from $\Sigma$.
Assuming that the set contains at least one non-empty string, the cardinality of the set produced by the Kleene star operator is infinite since we can always generate a new unique string by appending one of the non-empty strings.
-
$\begingroup$ Actually the Kleene closure applies to sets of strings, and the use with alphabets, i.e. sets of symbols, is an extension considering each alphabet as a set of strings of length 1.(just for the sake of precision). $\endgroup$ – babou Jun 16 '15 at 22:25
-
1$\begingroup$ Actually, it is not true that Kleene star always produces an infinite set. counterexamples: $\emptyset^*$, and $\{\varepsilon\}^*$. $\endgroup$ – Ran G. Jun 16 '15 at 22:31
