String

languages

Definition

String

A string $s\in {\Sigma }^{\ast }$ is a permutation of an alphabet $\Sigma$, where ${\Sigma }^{\ast }$ is the set of all permutations of $\Sigma$.

The empty string is commonly denoted as $\epsilon$ or $ϵ$.

Countability

Let $\Sigma =\{a_1,\dots a_k\}$ (a finite alphabet) and let ${\Sigma }^{\ast }$ be the (finite) set of all permutations of strings that can be created from $\Sigma$. Then, we can enumerate ${\Sigma }^{\ast }$ in the following way:

• List strings ordered by their length
• Within the same length, arrange them lexicographically

A bijective mapping $g:{\Sigma }^{\ast }\to \mathbb{N}$ is obtained by mapping each element in the enumerating to its position in the enumeration.

Enumeration:

Strings	Count	Positions
$\epsilon$ (empty string)	$1$	$0$
$a_1,\dots ,a_k$	$k$	$1,\dots ,k$
$a_1{a}_2,a_1{a}_2,\dots ,a_k{a}_k$	$k^2$	$k+1,\dots ,k^2+k$
$a_1{a}_1{a}_1,a_1{a}_1{a}_2,\dots ,a_k{a}_k{a}_k$	$k^3$	$k^2+k+1,\dots ,k^3+k^2+k$
$⋮$	$⋮$	$⋮$

Therefore, ${\Sigma }^{\ast }$ is countable.