String

languages

Definition

String

A string (or word) $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 $ϵ$.

Operations

Length

The length of a string $w$ is denoted as $|w|$.

Count Symbols

The number of certain symbols $a$ in a string $w$ is denoted as $|w{|}_a$, i.e.:

$$|w{|}_a=\left|\{s\in w\mid s\in a\}\right|$$

Concatenation

Let $a,b\in \Sigma$ be two strings, where $\Sigma$ is an alphabet, then:

$$[a]\cdot [b]=[ab]$$

with:

$$|ab|=|a|+|b|$$

Exponentiation

Let $w$ be a string, then:

$$w^0=\epsilon ,w^n=w{w}^{n-1}$$

where $\epsilon$ is the empty string.

Mirroring

Let $w=a_1{a}_2\dots a_{n-1}{a}_n$ be a string, then:

$$w^r=a_n{a}_{n-1}\dots a_2{a}_1$$

Empty

Definition

Empty String

The empty string a string of length $0$ and is denoted as $\epsilon$:

$$|\epsilon |=0$$

Link to original

Palindrome

Definition

Palindrome

A string is called palindrome iff:

$$w=w^r$$

where $w^r$ is the mirror image of $w$.

Link to original

Set of all Strings

Definition

Set of all Strings

The set of all strings ${\Sigma }^{\ast }$ over an alphabet $\Sigma$ is the set of all possible string concatenations on $\Sigma$.

Link to original

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.