-3
$\begingroup$

Suppose $Σ=\{0,1\}$; then $Σ^*$ is the set of all strings over $Σ$.

Is $Σ^*$ over $Σ$ finte?

$\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
1
$\begingroup$

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.

$\endgroup$
  • $\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

Not the answer you're looking for? Browse other questions tagged or ask your own question.