From a formal point of view, an **alphabet** is a non-empty set, denoted by the Latin capital letter \(\Sigma \) (“sigma”), whose elements are called **letters**.

We define the **concatenation** of any to letters $x,y\in\Sigma$ and denote this operation by the multiplication sign “\(\cdot\)”.

Using the concatenation, we can create **words**, also called **strings** \(s\) over the alphabet \(\Sigma\).

We denote by \(\Sigma^*\) the set of all strings over the alphabet \(\Sigma \).

Let $s\in\Sigma^*$ be a string. The **length** of the string, denoted by \(|s|\), is defined as the number of concatenated letters which were used to create the string $s$.

Please note that $|s|\ge 0$ for any $s\in\Sigma^*$. If \(|s|=0\), then we call $s$ the **empty string** and denote it by \(\epsilon\).

| | | | | created: 2014-06-22 15:42:14 | modified: 2020-05-09 21:01:11 | by: *bookofproofs* | references: [577]

[577] **Knauer Ulrich**: “Diskrete Strukturen – kurz gefasst”, Spektrum Akademischer Verlag, 2001