Foundations · Lesson 1

Words

A word over an alphabet $Σ$ is a finite sequence of letters of $Σ$ . We write a word of length $n$ as

w = w_{1} w_{2} \dots w_{n}

with each $w_{i} \in Σ$ . The length of $w$ is written $| w | = n$ .

Words are written without separators: the word 001001 is the sequence of six letters 0, 0, 1, 0, 0, 1, not a single number.

We group words by length: $Σ^{n}$ is the set of length- $n$ words, $Σ^{*}$ the set of all finite words (all lengths), and $Σ^{+}$ the set of all nonempty words. More precisely:

Σ^{n} = {w : | w | = n}, Σ^{*} = ⋃_{n \geq 0}^{} Σ^{n}, Σ^{+} = ⋃_{n \geq 1}^{} Σ^{n}

In particular, $Σ^{*}$ contains the empty word $ε$ (it has length $0$ ), while $Σ^{+}$ does not.

The empty word

The word with no letters is the empty word, written $ε$ . Its length is $0$ . It is a word over every alphabet.

Concatenation

Given two words $x$ and $y$ , their concatenation $x y$ is the word formed by writing all of $x$ followed by all of $y$ . For example, 01 · 001 = 01001, and $ε w = w ε = w$ for every word $w$ .

Length is additive under concatenation: $| x y | = | x | + | y |$ . For example, $| 01 | + | 001 | = 2 + 3 = 5 = | 01001 |$ .

1-based indexing

Positions in a word are numbered starting from $1$ , matching the notation $w [i .. j]$ for the factor from position $i$ to position $j$ :

If $i > j$ , then $w [i .. j] = ε$ : an empty range is the empty word.

For example, in 001001 we have $w [1 .. 3] = 001$ , $w [2 .. 4] = 010$ , and $w [1 .. 1] = 0$ . The empty range $w [4 .. 3]$ equals $ε$ .

Try it: inspect a word

Select a range in the word below and read off the letters at those positions:

Show indices