String

Definition

String

A string (or word) is a permutation of an alphabet , where is the set of all permutations of .

The empty string is commonly denoted as or .

Operations

Length

The length of a string is denoted as .

Count Symbols

The number of certain symbols in a string is denoted as , i.e.:

Concatenation

Let be two strings, where is an alphabet, then:

with:

Exponentiation

Let be a string, then:

where is the empty string.

Mirroring

Let be a string, then:

Empty

Definition

Empty String

The empty string is the unique string of length and is denoted as :

Link to original

Palindrome

Definition

Palindrome

A string is called palindrome iff:

where is the mirror image of .

Link to original

Set of all Strings

Definition

Set of all Strings

The set of all strings over an alphabet is the set of all possible string concatenations on .

Link to original

Countability

Let (a finite alphabet) and let be the (finite) set of all permutations of strings that can be created from . Then, we can enumerate in the following way:

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

A bijective mapping is obtained by mapping each element in the enumerating to its position in the enumeration.

Enumeration:

Strings	Count	Positions
(empty string)

Therefore, is countable.