Words and languages

Why languages

A compiler starts by reading a text: it must decide whether x1 is an identifier, whether 0x1F is a number, whether if (a) b; else c; is a statement. A search engine filters the lines that contain an email address. A network protocol checks that a message has the right shape. In all these cases, the question is the same: does this word belong to this set of words?

This course studies the simplest family of sets of words that is still useful: the regular languages. We describe them in two ways, and we shall learn to translate one into the other:

• by regular expressions, made to be written and read by humans (chapter 2);
• by finite automata, made to be run by machines (chapter 3).

Before that, we must fix the vocabulary: that is the purpose of this chapter.

Words

Alphabet and word

“Letters” are not necessarily characters. Depending on what we study, $\Sigma$ can be:

• $\{a, b\}$, for the examples of this course;
• $\{0, 1\}$, for binary numbers;
• the 128 ASCII characters, for a text analyser;
• $\{\texttt{if}, \texttt{else}, \texttt{id}, \texttt{(}, \texttt{)}, \texttt{;}\}$, for a parser that receives keywords already recognised.

What matters is that the alphabet is finite. Words, on the other hand, are infinitely many, but each one is finite.

Length

The length of a word $u$, written $|u|$, is its number of letters: $|abba| = 4$, $|\varepsilon| = 0$. For a letter $a$, we write $|u|_a$ for the number of occurrences of $a$ in $u$: $|abba|_a = 2$, $|abba|_b = 2$.

There are $|\Sigma|^n$ words of length $n$ over $\Sigma$: for each of the $n$ positions, we choose one letter among $|\Sigma|$. Over $\{a, b\}$, there is one word of length 0, two of length 1, four of length 2, eight of length 3.

Concatenation

With $u = ab$ and $v = ba$: $uv = abba$ and $vu = baab$. Concatenation has three properties you must know:

• it is associative: $(uv)w = u(vw)$, which lets us write $uvw$ without brackets;
• $\varepsilon$ is its neutral element: $u\varepsilon = \varepsilon u = u$;
• it is not commutative: $uv \neq vu$ in general, as we have just seen.

And lengths add up: $|uv| = |u| + |v|$.

We write $u^n$ for the word $u$ repeated $n$ times: $u^0 = \varepsilon$, and $u^{n+1} = u^n u$. Thus $(ab)^3 = ababab$, not to be confused with $ab^3 = abbb$: the exponent applies to what immediately precedes it.

Prefixes, suffixes, factors

A prefix is a factor with $w_1 = \varepsilon$, a suffix a factor with $w_2 = \varepsilon$. Every word is a prefix, a suffix and a factor of itself, and $\varepsilon$ is a prefix, a suffix and a factor of every word.

Subwords

$ac$ is a subword of $abc$, but not a factor. Every factor is a subword; the converse is false.

The transpose

The transpose (or mirror image) of $u$, written $u^t$ (sometimes $\tilde{u}$), is the word $u$ written backwards: $(abb)^t = bba$. We have $(uv)^t = v^t u^t$: the order is reversed, as for the transpose of a product of matrices. A word equal to its transpose is a palindrome: $abba$, $aba$, $\varepsilon$.

Languages

Definition

A language can be finite or infinite, and there is no reason for it to be “regular” in the everyday sense of the word.

Set operations

Since a language is a set, we have the set operations: union $L_1 \cup L_2$, intersection $L_1 \cap L_2$, difference $L_1 \setminus L_2$, complement $\overline{L} = \Sigma^* \setminus L$.

With the languages of the example: $L_2 \cap L_3$ contains the words that start with $a$ and have as many $a$ as $b$; $\overline{L_2}$ contains $\varepsilon$ and the words that start with $b$. The complement depends on the alphabet: you must always know what $\Sigma$ is.

Product of languages

The product inherits the properties of concatenation: it is associative, $\{\varepsilon\}$ is its neutral element, and it is not commutative ($\{a\}\{b\} = \{ab\}$, $\{b\}\{a\} = \{ba\}$). In addition it has an absorbing element, $\emptyset$: $L \cdot \emptyset = \emptyset \cdot L = \emptyset$, since no word can be chosen in $\emptyset$.

It is distributive over union: $L_1 (L_2 \cup L_3) = L_1 L_2 \cup L_1 L_3$. It is not distributive over intersection. With $L_1 = \{a, ab\}$, $L_2 = \{b\}$, $L_3 = \{\varepsilon\}$: $L_1(L_2 \cap L_3) = L_1 \cdot \emptyset = \emptyset$, whereas $L_1 L_2 \cap L_1 L_3 = \{ab, abb\} \cap \{a, ab\} = \{ab\}$.

Powers and star

We write $L^n$ for the product of $n$ copies of $L$: $L^0 = \{\varepsilon\}$, and $L^{n+1} = L^n \cdot L$. A word of $L^n$ is a concatenation of $n$ words of $L$, chosen independently.

This is the operation that takes us from the finite to the infinite: as soon as $L$ contains a non-empty word, $L^*$ is infinite. And it is where the notation $\Sigma^*$ comes from: seeing the alphabet as the language of one-letter words, $\Sigma^*$ is the set of words made of any number of letters, that is, of all words.

Two limit cases, which we shall meet again: $\emptyset^0 = \{\varepsilon\}$ by definition, and $\emptyset^n = \emptyset$ for $n \geq 1$. Hence

The star of the empty language is not empty: it contains the empty word, obtained by choosing no word at all.

A few identities, which can be checked by going back to the definitions:

Operations on words, extended to languages

All the notions of the first part extend to languages, word by word:

• $\mathrm{Pref}(L)$: the prefixes of the words of $L$;
• $\mathrm{Suff}(L)$: the suffixes of the words of $L$;
• $\mathrm{Fact}(L)$: the factors of the words of $L$;
• $L^t = \{u^t \mid u \in L\}$: the transpose of $L$.

For instance, $\mathrm{Pref}(\{ab, ba\}) = \{\varepsilon, a, ab, b, ba\}$. In chapter 6, we shall ask whether these operations preserve regular languages.

What next?

An infinite language cannot be written in extension: we cannot list its words. To talk about it, we need a finite description. The examples of this chapter have given several, in English (“the words that start with $a$”), in mathematical notation ($\{a^n b^n \mid n \geq 0\}$), or by operations ($\{a, ab\}^*$).

The last form is the right track: start from very simple languages and combine them by union, product and star. This is exactly what regular expressions do, in the next chapter.