4 Words, languages, sets-of-languages

Words, languages, and sets of languages are the objects we study in this course. In this chapter we define them and consider some basic properties. For the operations we consider on them see Chapter 5 and Chapter 6.

4.1 Words

A word is a finite sequence of symbols from a finite and non-empty set of available symbols (called alphabet). If the alphabet has only one symbol it is called unary, if it has exactly two binary. Usually the size of the alphabet will not matter much, but unary alphabets have sometimes slightly different properties than non-unary ones.

Words are often denoted by lowercase Latin letters, such as w or x. Alphabets are often denoted by capital Greek letters, such as \Sigma or \Gamma. To improve readability we use a special font for symbols in alphabets, that is \textcolor{darkred}{\mathtt{a}}, \textcolor{darkred}{\mathtt{b}}, \textcolor{darkred}{\mathtt{0}}, \textcolor{darkred}{\mathtt{1}}, etc. are symbols, while a, b, 0, 1 are not.

Example 4.1 \textcolor{darkred}{\mathtt{Hello\ world}} is a word over the alphabet of symbols that you can find on a standard US keyboard (see Figure 4.1), \textcolor{darkred}{\mathtt{101}} is a word over the binary alphabet \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}, and \textcolor{darkred}{\mathtt{GATTACA}} is a word in the alphabet of DNA bases \{\textcolor{darkred}{\mathtt{A}},\textcolor{darkred}{\mathtt{T}},\textcolor{darkred}{\mathtt{C}},\textcolor{darkred}{\mathtt{G}}\}.

We are interested in words since we are interested in the meaning associated to them.

Example 4.2 Words over \{\textcolor{darkred}{\mathtt{A}},\textcolor{darkred}{\mathtt{T}},\textcolor{darkred}{\mathtt{C}},\textcolor{darkred}{\mathtt{G}}\} can be associated with a sequence of nucleotides and possibly diseases or amino acids. Words over \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\} can be associated to binary numbers in the natural way. For this interpretation we use the notation \mathsf{value}_{2}(w) (see Chapter 1) and, for example, \mathsf{value}_{2}(\textcolor{darkred}{\mathtt{10011}})=19.

The length of a word w (denoted as \lvert w \rvert) is the number of symbols it contains. For i between 1 and \lvert w \rvert, we denote with w[i], the i-th symbol in w (and by convention we start counting from 1).

Example 4.3 The length of \textcolor{darkred}{\mathtt{Hello\ world}} is \lvert \textcolor{darkred}{\mathtt{Hello\ world}} \rvert=11, and the length of \textcolor{darkred}{\mathtt{101}} is \lvert \textcolor{darkred}{\mathtt{101}} \rvert=3.

Exercise 4.1 Show that the length of the binary representation of a number is logarithmic with respect to the number itself. That is, for every word w over the alphabet \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\} starting with a \textcolor{darkred}{\mathtt{1}},

\lvert w \rvert=\lfloor\log_2(\mathsf{value}_{2}(w))\rfloor+1\ .

The empty word (denoted by \varepsilon, “epsilon”) is the unique word that contains no symbols. We assume \varepsilon is never a symbol in the alphabet \Sigma. The length of the empty word is \lvert \varepsilon \rvert=0.

In some books the empty word is denoted by \lambda (“lambda”). The most common notation for the empty word is \varepsilon, for example this is the notations used in (Sipser 2013).

Definition 4.1 (subword) x is a subword of w if there are consecutive symbols in w that form x. If x appears at the beginning of w it is a prefix, if it appears at the end it is a suffix. |w|_x denotes the number of distinct occurrences of x in w as a subword.

Example 4.4 \textcolor{darkred}{\mathtt{cat}} is a subword of \textcolor{darkred}{\mathtt{caterpillar}}, and it is also a prefix. There are 3 occurrences of x=\textcolor{darkred}{\mathtt{aaa}} in w=\textcolor{darkred}{\mathtt{aaaaab}} (that is |w|_x=3): the occurrence of x that starts in w[1], the one that starts in w[2] and the one that starts in w[3].

Notice that \varepsilon is a subword of every word w, it is also a prefix of w and a suffix.

Exercise 4.2 Write a formal definition for the following informal descriptions of a logical property P(w). To define the property P(w) formally, use universal and existential quantifiers (\forall, \exists), Boolean operators (\lor, \land, \to, …) (see Chapter 1) and the notations about words above.

For instance, the property P(w) which informally is “w contains the subword \textcolor{darkred}{\mathtt{ab}}” can be formalized as

P(w)= \exists i\in \{1,\ldots, \lvert w \rvert-1\}\text{ s.t. }w[i]=\textcolor{darkred}{\mathtt{a}}\land w[i+1]=\textcolor{darkred}{\mathtt{b}}\ . or equivalently as P(w) = |w|_{\textcolor{darkred}{\mathtt{ab}}}>0\ .

To the right of every subword \textcolor{darkred}{\mathtt{ab}} in w there is some subword \textcolor{darkred}{\mathtt{ba}}.
Word w contains both the subword \textcolor{darkred}{\mathtt{ab}} and the subword \textcolor{darkred}{\mathtt{ba}}.
Between every two \textcolor{darkred}{\mathtt{b}}’s in w there is some \textcolor{darkred}{\mathtt{a}}.
Every occurrence of \textcolor{darkred}{\mathtt{b}} in w is in an even position (the first symbol of a word is in position 1).
Word w has some prefix with at least as many \textcolor{darkred}{\mathtt{b}}’s as \textcolor{darkred}{\mathtt{a}}’s.
In every prefix of w, the number of \textcolor{darkred}{\mathtt{b}}’s is at least the number of \textcolor{darkred}{\mathtt{a}}’s.
Word w has some even-length prefix with at least as many \textcolor{darkred}{\mathtt{b}}’s as \textcolor{darkred}{\mathtt{a}}’s.
Every even-length prefix of w has at least as many \textcolor{darkred}{\mathtt{b}}’s as \textcolor{darkred}{\mathtt{a}}’s.
Word w has a prefix and a suffix of the same nonzero length, equal to each other, and strictly less than the length of the word.
Word w is a palindrome, that is, w reads the same forwards as backwards, e.g. \textcolor{darkred}{\mathtt{madam}} or \textcolor{darkred}{\mathtt{rotator}} in English.

Exercise 4.3 Write the negation of the property P(w) for each of the properties defined in Exercise 4.2. For instance, the negation of the property P(w) that we used as an example is \begin{align*} \lnot P(w) &= \lnot (\exists i\in \{1,\ldots, \lvert w \rvert-1\}\text{ s.t. }w[i]=\textcolor{darkred}{\mathtt{a}}\land w[i+1]=\textcolor{darkred}{\mathtt{b}}) \\ &\equiv \forall i\in \{1,\ldots, \lvert w \rvert-1\}\ w[i]\neq \textcolor{darkred}{\mathtt{a}} \lor w[i+1]\neq \textcolor{darkred}{\mathtt{b}}\ , \end{align*} where \equiv means logical equivalence, that is the two logical expressions are true for the same words and false for the same words.

Exercise 4.4 Show that there is no word w\in \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}}\}^* s.t. \textcolor{darkred}{\mathtt{a}}w=w\textcolor{darkred}{\mathtt{b}}.

Exercise 4.5 Design at least two ways to encode a graph¹ as a word over a binary alphabet \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\} and compute explicitly the encoding of the complete graph on 3 vertices K_3. What is the length of the encoding of K_n for your two encodings as a function of n? Which one is more efficient?

4.2 Languages

A language is a set of words over a given alphabet. The language of all words over an alphabet \Sigma is denoted by \Sigma^*. On the opposite end, the language that contains no words is called the empty language and is just the empty set \emptyset.

Languages are often denoted by capital Latin letters, such as L or M.

Example 4.5 The set of all English words is a language over the English alphabet, and the set of all binary strings is a language over the binary alphabet.

Unlike words and alphabets, languages can be infinite sets (Exercise 4.6).

Exercise 4.6 Show that the language \Sigma^* is infinite for any alphabet \Sigma. What type of infinite? Show that \Sigma^* is countable.

Common errors

It is common to confuse \varepsilon with \emptyset. For example, \varepsilon\in \Sigma^* for any alphabet \Sigma but the empty language \emptyset is not a word, and thus \emptyset \notin \Sigma^* for any alphabet \Sigma.
Sentences such as “take an infinite word …” do not make sense, since words are always finite sequences of symbols.

The set of all infinite sequences of symbols over \Sigma is denoted by \Sigma^\omega and it is not a language, but an object of study in other branches of theoretical computer science. We do not study \Sigma^\omega in this course.

Exercise 4.7 Prove the following equalities between languages:

\{xy\in \{\textcolor{darkred}{\mathtt{a,b}}\}^* :|x|_{\textcolor{darkred}{\mathtt{a}}}=|y|_{\textcolor{darkred}{\mathtt{a}}}\}=\{w\in \{\textcolor{darkred}{\mathtt{a,b}}\}^*:|w|_{\textcolor{darkred}{\mathtt{a}}}\in 2\mathbb N\}.
\{xy\in \{\textcolor{darkred}{\mathtt{a,b}}\}^* :|x|_{\textcolor{darkred}{\mathtt{a}}}=|y|_{\textcolor{darkred}{\mathtt{b}}}\}=\{\textcolor{darkred}{\mathtt{a,b}}\}^*.
\{xy\in \{\textcolor{darkred}{\mathtt{a,b}}\}^* :|x|_{\textcolor{darkred}{\mathtt{aa}}}=|y|_{\textcolor{darkred}{\mathtt{b}}}\}=\{\textcolor{darkred}{\mathtt{a,b}}\}^*.
(🔥) \{w\in \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}^* :\mathtt{value}_2(ww^R)\in 3\mathbb N\}=\{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}^*

Exercise 4.8 Let L=\{w\in \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}^* :|w|_{\textcolor{darkred}{\mathtt{00}}}=0\}. Let Y\subseteq \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}^* be the minimal² set with the following properties:

\varepsilon,\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\in Y, and
if x,y\in Y, then x\textcolor{darkred}{\mathtt{1}}y\in Y.

Show that L=Y.

4.3 Sets of languages

In this course we are also interested in sets of languages, i.e., sets whose elements are languages. For example the set of languages with a given property, or the set of languages that can be recognized by a given type of machine. As a first non-trivial example, we consider \mathbf{Finite}, the set of all finite languges (over a fixed alphabet \Sigma).

For the rest of this section consider fixed an alphabet \Sigma.

Warning

Some properties of sets of languages might depend on the size of the alphabet. In particular, for unary alphabets some classes of languages might be equal, while for non-unary ones they are different. Unless stated otherwise we will always assume the classes of languages we consider are over non-unary alphabets.

In set theory the words set and class are not synonyms, but in this course we will use them as synonyms. In particular, we will not consider the technicalities of set theory that arise when considering classes of sets (or classes of languages) that are too large to be sets themselves.

Roughly speaking, we will group languages L according to the computational difficulty of the Membership problem for L, that is given as input a word w\in \Sigma^* and a description of L, we want to decide whether w\in L or not.

Example 4.6 The set of all languages over \Sigma is the set of all possible subsets of \Sigma^*, that is \mathscr{P}(\Sigma^*).

Exercise 4.9 (🔥) Show that the set \mathcal{P}(\Sigma^*) is uncountable for any alphabet \Sigma.

Given a class of languages \mathcal{C}, a derived class we can always construct from \mathcal{C} is the class \mathbf{co}\mathcal{C}: \mathbf{co}\mathcal{C}=\{L\subseteq \Sigma^* :\Sigma^*\setminus L \in \mathcal{C}\}\ , that is \mathbf{co}\mathcal{C} is the class of languages whose complement w.r.t. \Sigma^* is in \mathcal{C}.

For some classes of languages \mathcal{C}, we have \mathbf{co}\mathcal{C}=\mathcal{C}, for some others we will prove that they are different, while for others we simply don’t know. For example a famous open problem in complexity theory is whether \mathbf{co}\mathbf{NP}=\mathbf{NP}.

Exercise 4.10 Show that \mathbf{co}\mathbf{co}\mathcal{C}=\mathcal{C} for any class of languages \mathcal{C}.

4.3.1 Finite – all the finite languages

The first non-trivial class of languages we consider is \mathbf{Finite}, the set of all finite languages over \Sigma. The Membership problem (see Section 4.3) for such languages is very easy: we just have a finite case of options to check.

Example 4.7 The empty language \emptyset is a finite language (it contains 0 words), and thus \emptyset \in \mathbf{Finite}. However, the language \Sigma^* is not a finite language, and thus \Sigma^* \notin \mathbf{Finite}.

Exercise 4.11 Show that for any alphabet \Sigma,

\mathbf{Finite} is countable.
\mathbf{co}\mathbf{Finite} is countable.

This is a general phenomenon for the classes of languages we will see in this course, they will be always countable, and in particular (due to Exercise 4.9) never equal to \mathscr{P}(\Sigma^*).

Exercise 4.12 Show that \mathbf{Finite} and \mathbf{co}\mathbf{Finite} have empty intersection.

Exercise 4.13 Give an example of language in \mathscr{P}(\Sigma^*) that is not in \mathbf{Finite} and not in \mathbf{co}\mathbf{Finite}.

One would be tempted to say that the languages in \mathbf{Finite} or \mathbf{co}\mathbf{Finite} are very easy. In some sense they are, but in some other sense it might be very hard to prove that a given language belongs to one of these classes.

Exercise 4.14 (Easy languages from hard conjectures) In this exercise we consider two languages that are defined in terms of famous open conjectures in number theory, and we show that they belong to \mathbf{Finite}\cup\mathbf{co}\mathbf{Finite}:

L_G is connected to the famous Goldbach’s conjecture;
L_\pi is connected to the question of whether \pi is a normal number.

Let L_G be the following language over the binary alphabet \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}: L_G=\{w\in \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}^* :\exists p\in \mathbb{N}\text{ s.t. }p\geq \mathsf{value}_{2}(w)\land p,p+2\in \mathbb{P}\}\ , where \mathsf{value}_{2}(w) is the natural number represented by the binary string w and \mathbb{P} is the set of prime numbers. Show that L_G is in \mathbf{Finite}\cup\mathbf{co}\mathbf{Finite}. Does L_G belong to \mathbf{Finite}?
Let L_\pi be the following language over the unary alphabet \{\textcolor{darkred}{\mathtt{0}}\}: L_\pi=\{w\in \{\textcolor{darkred}{\mathtt{0}}\}^* :\text{the binary expansion of $\pi$ contains $w$}\}\ . Show that L_\pi is in \mathbf{Finite}\cup\mathbf{co}\mathbf{Finite}.

Recall that a (directed) graph is a pair (V,E) where V is a set of vertices and E\subseteq \binom{V}{2} is a set of edges. You can assume that the vertices are numbered from 1 to n for some n\in \mathbb{N}.↩︎
Recall that minimal means that it is the smallest set with the given properties. That is, any other set with the same properties must contain it.↩︎