4
$\begingroup$

Suppose we have an alphabet $\Sigma$, does $\Sigma^*$ contain an infinite string? My reasoning is, since $\Sigma^*$ contains an infinite number of strings, one of those strings must have an infinite length, assuming there is no restriction on the length of strings.

My professor says that's wrong, and an automata can only process finite length strings. Is he correct?

As a corollary, suppose $\Sigma$ contains an infinite alphabet. Does $\Sigma^*$ contain an infinite string?

My answer was yes for that too, since a string might contain all elements from the alphabet and since the alphabet is infinite, the string must be too. But my professor says I'm wrong here too.

Can someone explain why he said that and where I'm going wrong here?

$\endgroup$
1
  • $\begingroup$ You may be interested in knowing that the set of all infinite strings over $\Sigma$ is usually denoted $\Sigma^{\omega}$. See more here. $\endgroup$
    – mrp
    Sep 7, 2015 at 7:28

3 Answers 3

3
$\begingroup$

Your main mistake is right here:

My reasoning is, since $\Sigma^*$ contains an infinite number of strings, one of those strings must have an infinite length, assuming there is no restriction on the length of strings.

Consider the alphabet $\Sigma=\{a\}$. There is one string of length $0$: the empty string. There is one string of length $1$: $a$. There is one string of length $2$: $aa$. In fact, for each non-negative integer $n$ there is exactly one string of length $n$: $\underbrace{aaa\ldots aaa}_{n\text{ copies}}$.

There are no infinite integers, so each string is finite, but there are infinitely many strings in $\Sigma^*$.

The automata that you’re studying are defined in such a way that they process only finite strings. People have defined and studied automata that process infinite strings, but they are a significantly more advanced topic. In the context of what you’re studying, your professor is correct.

Whether $\Sigma$ is finite or not, the elements of $\Sigma^*$ are by definition the finite strings of members of $\Sigma$, so by definition $\Sigma^*$ does not contain any infinite words.

$\endgroup$
2
  • $\begingroup$ Thanks a lot, that really cleared things up. I'd upvote everyone in this thread, but I don't have enough rep. $\endgroup$
    – cybergla
    Sep 7, 2015 at 7:32
  • $\begingroup$ You’re welcome; I’ll upvote the other two in your stead. :-) $\endgroup$ Sep 7, 2015 at 7:35
2
$\begingroup$

The Kleene closure is defined to only have finite strings.

There are an infinite number of such strings, just as there are an infinite number of integers.

However, each individual string is finite, just like each individual integer is finite.

Having an infinite alphabet is complete unrelated to the length of the strings. A string from the Kleene closure can not contain every character from an infinte alphabet.

$\endgroup$
1
$\begingroup$

$\Sigma^*$ is, by definition, the smallest set containing $\Sigma$, the empty word, and stable by concatenation. With that, you cannot reach infinite strings.

In other words, $\Sigma^*$ is the set of all finite strings on $\Sigma$.

$\endgroup$

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.