Strings

An alphabet is a finite set of symbols such as $\lbrace0, 1\rbrace$ and $\lbrace a, b, \ldots, z \rbrace$ . A string is a finite sequence of symbols drawn from a given alphabet. For example, ‘aa’, ‘cat’, ‘abracadabra’ are examples of strings over the alphabet of lowercase letters, of length 2, 3, and 11 respectively. The empty string $\epsilon$ has length 0.

Consider recursive construction of the set of strings of length $n$ over alphabet $\Sigma$ .¹ If $n=0$ , the set is $\lbrace\epsilon\rbrace$ , consisting of only the empty string. If $n> 0$ , for each symbol $a\in\Sigma$ , prepend $a$ to every string of length $n-1$ , where these strings are generated recursively. Since each of $n$ positions can be occupied by $|\Sigma|$ possible symbols, there are $|\Sigma|^n$ strings of length $n$ in total. For example, for $\Sigma = \lbrace 0, 1\rbrace$ and $n=3$ , there are $2^3=8$ strings:

The following program generates such a table of strings in the form of a keyboard. Each symbol is color-coded, being represented by a rectangle whose color distinguishes it from the other symbols. Use base to select the size of the alphabet and n to select the string length. For example, for base=2, red corresponds to 0 and blue to 1; for base=3, red, green, and blue correspond to the symbols 0, 1, and 2 respectively.

A keyboard of strings

Prev Next

Convention is to use $\Sigma$ to denote the alphabet. ↩

Michael Laszlo

It is not a something, but not a nothing either

Strings