Strings

We build strings from some alphabet/lexicon $\Sigma$.

Strings of length $N$ are given by $\Sigma^N$ and the Kleene closure of $\Sigma$—notated $\Sigma^*$—gives us the set of all finite strings over $\Sigma$.

\[\Sigma^* \equiv \bigcup_{i\in\mathbb{N}} \Sigma^i\]

Note that $\Sigma^0 = \{\varepsilon\}$, where $\varepsilon$ denotes the empty string—the unique string of length zero. It is important not to confuse the empty string $\varepsilon$ (which is an element of $\Sigma^*$) with the empty set $\emptyset$ (which contains no elements at all) or with the empty language $\emptyset \subset \Sigma^*$ (a language with no strings in it). The set $\{\varepsilon\}$ is not empty—it contains exactly one string, the empty string. This distinction will matter throughout the course: $\varepsilon$ is a string, $\emptyset$ is a set.

Question

If $|\Sigma| = 3$, how many strings are in $\Sigma^0$? In $\Sigma^1$? In $\Sigma^2$? What about $\Sigma^k$ in general? Is $\Sigma^*$ finite or infinite?

Answer

As an infinite set, we need to implement $\Sigma^*$ using a generator. We’ll start by defining a function that produces $\Sigma^i$.

from collections.abc import Iterator, Sequence
from itertools import product

def sigma_i(sigma: Sequence[str], i: int) -> Iterator[tuple[str, ...]]:
    """Generate the strings of length ``i`` over ``sigma``."""
    if i < 0:
        raise ValueError("i must be nonnegative")
    sigma_repeated = [sigma] * i
    return product(*sigma_repeated)

sigma: tuple[str, ...] = ("ɹ", "d", "u")

for s in sigma_i(sigma, 3):
    print(''.join(s))

We can then define $\Sigma^*$ using a generator comprehension.

Generator for natural numbers

def natural_numbers() -> Iterator[int]:
    """Yield the natural numbers starting with zero."""
    i = 0
    while True:
        yield i
        i += 1

sigma_star = (''.join(s) 
              for i in natural_numbers() 
              for s in sigma_i(sigma, i))

for s in sigma_star:
    if len(s) < 4:
        print(s)
    else:
        break

Question

How many strings are there in $\Sigma^*$ (assuming that $\Sigma$ is finite and nonempty)? That is, what is $|\Sigma^*| = |\bigcup_{i\in\mathbb{N}} \Sigma^i|$?

So how do we answer the question? We can construct a length-lexicographic enumeration (LLE): list the empty string first, then all strings of length $1$, then all strings of length $2$, and so on, using a fixed lexicographic order within each length. This will show that $|\Sigma^*|=|\mathbb{N}|$.

First, $\Sigma^*$ is infinite. Fix any symbol $a\in\Sigma$. The map $i\mapsto a^i$ is an injection from $\mathbb{N}$ to $\Sigma^*$ because $a^i$ and $a^j$ have different lengths whenever $i\neq j$. Thus, $|\Sigma^*|\geq|\mathbb{N}|$.

Second, the LLE assigns each string a unique natural-number position. Let $m=|\Sigma|$ and define

\[C_i=\sum_{j=0}^{i-1}m^j.\]

The number $C_i$ is the count of strings shorter than $i$. We reserve the block

\[N_i=\{C_i,C_i+1,\ldots,C_i+m^i-1\}\]

for the strings in $\Sigma^i$. This block has exactly $m^i=|\Sigma^i|$ positions. It ends at $C_i+m^i-1=C_{i+1}-1$, so the next block begins immediately at $C_{i+1}$. Thus, the blocks are disjoint and together cover every natural number.

You can get an idea for how this works by enumerating the strings we generate from sigma_star.

N = natural_numbers()

sigma_star = (''.join(s) 
              for i in N 
              for s in sigma_i(sigma, i))

for j, s in enumerate(sigma_star):
    if len(s) < 5:
        print(j, s)
    else:
        break

For instance, when $m=3$, $N_0=\{0\}$, $N_1=\{1,2,3\}$, and $N_2=\{4,\ldots,12\}$. These are exactly the blocks visible in the output above.

Now impose an arbitrary order on the finite alphabet $\Sigma$. This order induces a lexicographic order on each finite set $\Sigma^i$, so there is a bijection $S_i:N_i\to\Sigma^i$. Define $k:\mathbb{N}\to\mathbb{N}$ so that $k(n)$ is the unique length $i$ for which $n\in N_i$, and stitch the within-length maps together:

\[S_*(n) = S_{k(n)}(n)\]

It remains to verify both directions. For injectivity, suppose $S_*(n)=S_*(n')$. Equal strings have equal lengths, so $k(n)=k(n')=i$. Both positions are thus in $N_i$, and the injectivity of $S_i$ gives $n=n'$. For surjectivity, fix an arbitrary $w\in\Sigma^*$. It has some finite length $i$, so $w\in\Sigma^i$. Since $S_i$ is surjective, some $n\in N_i$ satisfies $S_i(n)=w$, and hence $S_*(n)=w$.

Thus, $S_*$ is a bijection from $\mathbb{N}$ to $\Sigma^*$. We have shown both inequalities constructively, and we conclude that $|\Sigma^*|=|\mathbb{N}|$ for every finite nonempty alphabet. If $\Sigma=\emptyset$, the exception is $\Sigma^*=\{\varepsilon\}$, which is finite.

--- title: Strings jupyter: python3 --- We build strings from some alphabet/lexicon $\Sigma$. Strings of length $N$ are given by $\Sigma^N$ and the [**Kleene closure**](https://en.wikipedia.org/wiki/Kleene_star) of $\Sigma$—notated $\Sigma^*$—gives us the set of all finite strings over $\Sigma$. $$\Sigma^* \equiv \bigcup_{i\in\mathbb{N}} \Sigma^i$$ Note that $\Sigma^0 = \{\varepsilon\}$, where $\varepsilon$ denotes the *empty string*—the unique string of length zero. It is important not to confuse the empty string $\varepsilon$ (which is an element of $\Sigma^*$) with the empty set $\emptyset$ (which contains no elements at all) or with the empty *language* $\emptyset \subset \Sigma^*$ (a language with no strings in it). The set $\{\varepsilon\}$ is not empty—it contains exactly one string, the empty string. This distinction will matter throughout the course: $\varepsilon$ is a string, $\emptyset$ is a set. ::: {.callout-caution} ## Question If $|\Sigma| = 3$, how many strings are in $\Sigma^0$? In $\Sigma^1$? In $\Sigma^2$? What about $\Sigma^k$ in general? Is $\Sigma^*$ finite or infinite? ::: ::: {.callout-tip collapse=true} ## Answer $|\Sigma^0| = 1$ (just the empty string), $|\Sigma^1| = 3$, $|\Sigma^2| = 9$, and in general $|\Sigma^k| = 3^k$. Since the alphabet is finite and nonempty, $\Sigma^*$ is countably infinite. We construct the required bijection below rather than assuming that every countable union is countable. ::: As an infinite set, we need to implement $\Sigma^*$ using a generator. We'll start by defining a function that produces $\Sigma^i$. ```{python} #| colab: {base_uri: 'https://localhost:8080/'} #| executionInfo: {elapsed: 181, status: ok, timestamp: 1643219172265, user: {displayName: Aaron Steven White, photoUrl: 'https://lh3.googleusercontent.com/a-/AOh14GjIthWcbbAkpz4qrGfqtOGZvudhRK2mQl0LCAJjbw=s64', userId: 06256629009318567325}, user_tz: 300} #| outputId: 00baa0be-47d1-403f-b8e9-9982f849a890 from collections.abc import Iterator, Sequence from itertools import product def sigma_i(sigma: Sequence[str], i: int) -> Iterator[tuple[str, ...]]: """Generate the strings of length ``i`` over ``sigma``.""" if i < 0: raise ValueError("i must be nonnegative") sigma_repeated = [sigma] * i return product(*sigma_repeated) sigma: tuple[str, ...] = ("ɹ", "d", "u") for s in sigma_i(sigma, 3): print(''.join(s)) ``` We can then define $\Sigma^*$ using a generator comprehension. ```{python} #| code-fold: true #| code-summary: Generator for natural numbers def natural_numbers() -> Iterator[int]: """Yield the natural numbers starting with zero.""" i = 0 while True: yield i i += 1 ``` ```{python} #| colab: {base_uri: 'https://localhost:8080/'} #| executionInfo: {elapsed: 171, status: ok, timestamp: 1643219179301, user: {displayName: Aaron Steven White, photoUrl: 'https://lh3.googleusercontent.com/a-/AOh14GjIthWcbbAkpz4qrGfqtOGZvudhRK2mQl0LCAJjbw=s64', userId: 06256629009318567325}, user_tz: 300} #| outputId: 3040ebc6-db96-4e19-ad5f-0a1672e7b8bf sigma_star = (''.join(s) for i in natural_numbers() for s in sigma_i(sigma, i)) for s in sigma_star: if len(s) < 4: print(s) else: break ``` ::: {.callout-caution} ## Question How many strings are there in $\Sigma^*$ (assuming that $\Sigma$ is finite and nonempty)? That is, what is $|\Sigma^*| = |\bigcup_{i\in\mathbb{N}} \Sigma^i|$? ::: So how do we answer the question? We can construct a **length-lexicographic enumeration** (LLE): list the empty string first, then all strings of length $1$, then all strings of length $2$, and so on, using a fixed lexicographic order within each length. This will show that $|\Sigma^*|=|\mathbb{N}|$. First, $\Sigma^*$ is infinite. Fix any symbol $a\in\Sigma$. The map $i\mapsto a^i$ is an injection from $\mathbb{N}$ to $\Sigma^*$ because $a^i$ and $a^j$ have different lengths whenever $i\neq j$. Thus, $|\Sigma^*|\geq|\mathbb{N}|$. Second, the LLE assigns each string a unique natural-number position. Let $m=|\Sigma|$ and define $$C_i=\sum_{j=0}^{i-1}m^j.$$ The number $C_i$ is the count of strings shorter than $i$. We reserve the block $$N_i=\{C_i,C_i+1,\ldots,C_i+m^i-1\}$$ for the strings in $\Sigma^i$. This block has exactly $m^i=|\Sigma^i|$ positions. It ends at $C_i+m^i-1=C_{i+1}-1$, so the next block begins immediately at $C_{i+1}$. Thus, the blocks are disjoint and together cover every natural number. You can get an idea for how this works by enumerating the strings we generate from `sigma_star`. ```{python} #| colab: {base_uri: 'https://localhost:8080/'} #| executionInfo: {elapsed: 226, status: ok, timestamp: 1643219187279, user: {displayName: Aaron Steven White, photoUrl: 'https://lh3.googleusercontent.com/a-/AOh14GjIthWcbbAkpz4qrGfqtOGZvudhRK2mQl0LCAJjbw=s64', userId: 06256629009318567325}, user_tz: 300} #| outputId: a33a5267-d0fc-49ed-add2-5f1d14f7f7bd N = natural_numbers() sigma_star = (''.join(s) for i in N for s in sigma_i(sigma, i)) for j, s in enumerate(sigma_star): if len(s) < 5: print(j, s) else: break ``` For instance, when $m=3$, $N_0=\{0\}$, $N_1=\{1,2,3\}$, and $N_2=\{4,\ldots,12\}$. These are exactly the blocks visible in the output above. Now impose an arbitrary order on the finite alphabet $\Sigma$. This order induces a lexicographic order on each finite set $\Sigma^i$, so there is a bijection $S_i:N_i\to\Sigma^i$. Define $k:\mathbb{N}\to\mathbb{N}$ so that $k(n)$ is the unique length $i$ for which $n\in N_i$, and stitch the within-length maps together: $$S_*(n) = S_{k(n)}(n)$$ It remains to verify both directions. For injectivity, suppose $S_*(n)=S_*(n')$. Equal strings have equal lengths, so $k(n)=k(n')=i$. Both positions are thus in $N_i$, and the injectivity of $S_i$ gives $n=n'$. For surjectivity, fix an arbitrary $w\in\Sigma^*$. It has some finite length $i$, so $w\in\Sigma^i$. Since $S_i$ is surjective, some $n\in N_i$ satisfies $S_i(n)=w$, and hence $S_*(n)=w$. Thus, $S_*$ is a bijection from $\mathbb{N}$ to $\Sigma^*$. We have shown both inequalities constructively, and we conclude that $|\Sigma^*|=|\mathbb{N}|$ for every finite nonempty alphabet. If $\Sigma=\emptyset$, the exception is $\Sigma^*=\{\varepsilon\}$, which is finite.