5 Operations on words
In this chapter we introduce some operations on words that we will use in the rest of the course. In particular we introduce the concatenation of words, the reverse of a word, and homomorphisms between sets of words.
5.1 Concatenation
The main operation on words is concatenation. The concatenation of two words w and x is the word obtained by writing w followed by x. It is denoted by wx (or w\cdot x).
For example, the concatenation of \textcolor{darkred}{\mathtt{hello}} and \textcolor{darkred}{\mathtt{world}} is \textcolor{darkred}{\mathtt{helloworld}}, and the concatenation of \textcolor{darkred}{\mathtt{101}} and \textcolor{darkred}{\mathtt{11}} is \textcolor{darkred}{\mathtt{10111}}.
Exercise 5.1 (Algebraic properties) Show the following basic algebraic properties of concatenation. For all words x,y,z\in \Sigma^*
- (xy)z = x(yz), that is the concatentation is associative.
- \varepsilon x = x\varepsilon= w, that is the empty word is the identity element for concatenation.
- if xy = yx holds for every x,y\in \Sigma^*, then |\Sigma|=1. That is if |\Sigma|\geq 2 then the concatenation is not commutative.
Exercise 5.2 Show that the length of the concatenation of two words w and x is the sum of their lengths, i.e., \lvert wx \rvert = \lvert w \rvert + \lvert x \rvert.
Exercise 5.3 (Cancellation law) Show that if wx = wy, then x = y (i.e., we can “cancel” w from the left), and if xw = yw, then x = y (i.e., we can “cancel” w from the right).
5.2 n-th power of a word
For n\in \mathbb{N} at least 1, w^n denotes the word w concatenated with itself n times and w^0=\varepsilon.
When \textcolor{darkred}{\mathtt{1}}\in \Sigma, a common error is to confuse \textcolor{darkred}{\mathtt{1}}^n, that is the concatenation of the word \textcolor{darkred}{\mathtt{1}} with itself n times, with 1^n, the n-th power of the number 1.
Exercise 5.4 Show that for n\in \mathbb N, |w^n|=n|w|.
5.3 Reverse
The reverse of a word w over \Sigma is the language word w^R obtained by writing w in reverse, that is \varepsilon^R=\varepsilon and (\textcolor{darkred}{\mathtt{s}}u)^R=u^R\textcolor{darkred}{\mathtt{s}} for every \textcolor{darkred}{\mathtt{s}}\in \Sigma and u\in \Sigma^*.
Exercise 5.5 Show that for every word w, (w^R)^R=w.
Exercise 5.6 Show that for every two words w and z, (wz)^R=z^Rw^R.
5.4 Homomorphisms
Given two sets A,B and operations \circ_A and \circ_B on A and B respectively, a homomorphism from (A,\circ_A) to (B,\circ_B) is a function f:A\to B that preserves the operations, that is for every x,y\in A, f(x\circ_A y)=f(x)\circ_B f(y).
Example 5.1 Homomorphisms are everywhere in mathematics. For instance, some examples of homomorphism (that you for sure already know) are the following:
- the function n\mapsto 2^n is a homomorphism from (\mathbb{N},+) to (\mathbb{N},\cdot), since for every n,m\in \mathbb{N}, 2^{n+m}=2^n\cdot 2^m.
- the function n\mapsto \log_2(n) is a homomorphism from (\mathbb{N}\setminus\{0\},\cdot) to (\mathbb{R},+), since for every n,m\in \mathbb{N}\setminus\{0\}, \log_2(n\cdot m)=\log_2(n)+\log_2(m).
- Exercise 5.2 can be restated as the length function of words is a homomorphism from (\Sigma^*,\cdot) to (\mathbb{N},+).
In the context of this course, we are interested in homomorphisms between (\Sigma^*,\cdot) and (\Gamma^*,\cdot), where \Sigma and \Gamma are alphabets and \cdot is the concatenation operation. That is, a function \sigma:\Sigma^*\to\Gamma^* is a homomorphism if for every two words u,v\in \Sigma^*, \sigma(uv)=\sigma(u)\sigma(v).
For the rest of this section (and the rest of this course) when we say that \sigma is a homomorphism, we mean that \sigma:(\Sigma^*,\cdot)\to(\Gamma^*,\cdot) is a homomorphism for some alphabets \Sigma and \Gamma.
Example 5.2 (The ASCII code as a homomorphism) The ASCII code is a homomorphism that maps words on the standard US keyboard to words on the binary alphabet \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\} given by the ASCII code. For example, it maps the word \textcolor{darkred}{\mathtt{Hello\ world}} to the binary string 0100100001100101011011000110110001101111001000000101011101101111011100100110110001100100, which is the concatenation of the ASCII codes of the symbols in \textcolor{darkred}{\mathtt{Hello\ world}}.
org/wiki/British_and_American_keyboards#/media/File:KB_United_States-NoAltGr.svg){kind=link}
The homomorphism for Example 5.2 is injective (aka 1-to-1), that is different words are mapped to different binary strings. That is given a binary string, there is a unique word that maps to it. For example, what is the word represented by the binary string 010010010010000001101100011011110111011001100101001000000101010001000011?1.
Homorphisms are functions \sigma:(\Sigma^*,\cdot)\to(\Gamma^*,\cdot) that are easy to describe, since it is enough to specify \sigma(\textcolor{darkred}{\mathtt{s}}) for every symbol \textcolor{darkred}{\mathtt{s}}\in \Sigma, and then the value of \sigma on any word w is determined by the homomorphism property. For example, to define the ASCII code homomorphism, it is enough to specify the binary string that corresponds to each symbol on the standard US keyboard.
Homomorphisms in general can be non-injective, for example the homomorphism \sigma:\{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}}\}^*\to \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}^* defined by \sigma(\textcolor{darkred}{\mathtt{a}})=\textcolor{darkred}{\mathtt{0}} and \sigma(\textcolor{darkred}{\mathtt{b}})=\textcolor{darkred}{\mathtt{0}} maps every word to a string of \textcolor{darkred}{\mathtt{0}}s, and it is easy to see that it is not injective.
Exercise 5.7 (Homomorphisms or not?) Which of the following functions \sigma:\Sigma^*\to\Sigma^* are homomorphisms?
- \sigma(w)=w.
- \sigma(w)=w^R.
- \sigma(w)=\varepsilon.
- \sigma(w)=\sigma_1(\sigma_2(w)), where \sigma_1,\sigma_2 are homomorphisms from \Sigma^* to \Gamma^*.
- \sigma(w)=ww.
- \sigma(w)=\textcolor{darkred}{\mathtt{a}}^{|w|}, where \textcolor{darkred}{\mathtt{a}}\in \Sigma.
- \sigma(w)=\tau^{-1}(w) where \tau is a homomorphism.2
- \sigma(w)=|w|_{\textcolor{darkred}{\mathtt{s}}} where \textcolor{darkred}{\mathtt{s}}\in \Sigma.
- \sigma(w)=|w|_{x} where x\in \Sigma^*.
- \sigma(w)=w[1]w[1]w[2]w[2]\cdots w[|w|]w[|w|].
Exercise 5.8 (Words over a noisy channel) You want to transmit words w\in \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}},\textcolor{darkred}{\mathtt{c}}\}^* over a noisy channel that can only transmit words over the binary alphabet \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}. You want to use a homomorphism \sigma:\{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}},\textcolor{darkred}{\mathtt{c}}\}^*\to \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}^* to encode the words before transmitting them in such a way that the original word can be recovered from the transmitted one if the channel introduces at most one error (a bit flipped from \textcolor{darkred}{\mathtt{0}} to \textcolor{darkred}{\mathtt{1}} or vice versa) in the transmitted string. What is a good choice of \sigma?