Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Are the number of finite-length strings created with a finite alphabet finite or infinite?

I assume the answer is quite simple and straightforward, but I do not know the correct wording or lingo find and understand the answer. (I am an engineer and not a mathematician.)

Implications

  • The number of possible books that can exist
  • The number of songs that can be composed
  • The number of unique images that can be captured
  • The number of possible finite-sized universes
share|improve this question

5 Answers 5

up vote 0 down vote accepted

There are infinitely many such finite-length strings, although only finitely many of any given length. To see this, note that there is at least one string of each length, and there are infinitely many (in fact $|\mathbb{N}|$) possible lengths.

share|improve this answer
1  
Since the "infinitely many possible lengths" is countably infinite, then I assume the number of such strings is also countably infinite? –  nicholas Sep 6 '12 at 16:05
1  
Indeed - this remains true even if your alphabet is countably infinite. –  Matt Pressland Sep 6 '12 at 16:05
    
@nicholas But be careful, of course - there are countably many strings of finite length, but not countably many strings of countable length! (as long as your alphabet has more than one symbol). –  Steven Stadnicki Sep 6 '12 at 17:13

Infinite. There are an infinite number of possible finite lengths. Say the alphabet has one word "a". My first book is "a", my second is "a a", the third is "a a a", so on an so forth. Each one is finite, but there are an infinite number.

share|improve this answer

Supopse you have an alphabet of size $m$ and want to create strings of length exactly $n$. This can be accomplished in $m^n$ ways. Thus, the number of strings with length at most $n$ is $$ \sum_{k = 1}^n m^k. $$

In theory, there is no limit to the length of a book, since there is no limit to how big $m$ or $n$ can be (I can always invent a new symbol or write another page). It is true there are an infinite number of finite-length strings.

Practically, however, a human brain can only understand so many symbols and there is only so much matter in the universe with which to write a book, so this puts a bound on both $m$ and $n$.

share|improve this answer
1  
+1 for adding the perspective on "practical lengths" - I suppose the key distinction to making these sets finite is having a specified (not-arbitrary) finite length –  nicholas Sep 6 '12 at 16:09
    
Clearly you have not looked at the Federal tax code. It is unbounded in every way except understanding. –  copper.hat Sep 6 '12 at 17:14

The answer is countably infinite.

Suppose you have an alphabet $\Sigma$ with $n = |\Sigma|$ symbols. $\Sigma^k$ denotes the set of (exactly) $k$-length strings, and $\Sigma^* = \cup_{k=0}^\infty \Sigma^k$ denotes the set of finite strings over $\Sigma$. $\Sigma^0$ denotes the set containing the empty string, ie, $\Sigma^0 = \{ \epsilon \}$.

Order the symbols in $\Sigma = \{ \sigma_1, ..., \sigma_n \}$, and define $\nu : \Sigma \to \{0,...,n-1\}$ by $\nu(\sigma_k) = k-1$. Then define $\phi: \Sigma^* \to \mathbb{N}\cup \{0\}$ by $\phi(\epsilon) = 0$, and $\phi(\alpha_1 \cdots \alpha_l) = \frac{n^l -1 } {n-1}+\sum_{k=1}^l \nu(\alpha_k) n^{k-1}$, for $l \geq 1$. A bit of work shows that $\phi$ is a bijection, hence $\Sigma^*$ is countably infinite.

(Note that the bijection is 'almost' the base-$n$ value of the string, but must allow for the fact that, for example, the strings $0$ and $000$ are different while their base-$n$ value is the same. In the above, with $\Sigma = \{0,1\}$, $\phi(0) = 1$, $\phi(000) = 7$.)

Unfortunately, this trick doesn't generalize to countable alphabets.

share|improve this answer

Length of your string is a natural number. For each length you can make at least one string of that length. So total number of strings is infinite. It is countably infinite for finite alphabet.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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