6  Operations on languages

In this chapter consider fixed an alphabet \Sigma. We consider operations on languages over \Sigma, that is on subsets of \Sigma^*.

6.1 Set-theoretic operations

Since languages are sets you can do on them all usual operations available on sets:

  • union \cup,
  • intersection \cap,
  • complement \overline{\phantom{A}} (w.r.t. \Sigma^*),
  • the image of a set under a function, for example a homomorphism (see Section 5.4),
  • the inverse image of a set under a function, for example a homomorphism.

Exercise 6.1 Given a homomorphism \sigma, is it true that if \sigma is injective then |\sigma(L)|=|L|?

6.2 Reverse

The reverse of a language L is the language L^R=\{w^R:w\in L\}\ .

Exercise 6.2 Show that for a finite L, |L^R|=|L|.

Exercise 6.3 Given languages L_1,L_2\subseteq \Sigma^*, which of the following equalities are always true?

  1. (L_1\cup L_2)^R=L_1^R\cup L_2^R, that is the reverse distributes over union.

  2. (L_1\cap L_2)^R=L_1^R\cap L_2^R, that is the reverse distributes over intersection.

  3. \overline{L}^R=\overline{L^R}, that is the complement and the reverse of a language commute.

6.3 Concatenation

Given languages L_1,L_2, the language concatenation of them is L_1\cdot L_2 =\{u\cdot v :u\in L_1 \land v\in L_2 \}\ , that is L_1\cdot L_2 (or simply L_1 L_2) consists of all word obtained concatenating one word of L_1 followed by one word of L_2 in all the possible ways.

Exercise 6.4 Show that

  1. L\emptyset=\emptyset. (And similarly \emptyset L=\emptyset.)
  2. L\{\varepsilon\}=L. (And similarly \{\varepsilon\} L=L.)

Exercise 6.5 Give examples of languages L_1,L_2 s.t. L_1 L_2 \neq L_2 L_1 and s.t. L_1 L_2 = L_2 L_1.

Exercise 6.6 Show that (L_1L_2)L_3=L_1(L_2L_3) for all languages L_1, L_2, and L_3.

Exercise 6.7 Give an example of finite languages L_1, L_2 s.t. |L_1L_2|\neq |L_1|\cdot |L_2|.

Exercise 6.8 (Concatenation vs reverse) Given two languages L_1,L_2\subseteq \Sigma^*, which of the following sentences are true?

  1. (L_1L_2)^R=L_2^RL_1^R.

  2. If (L_1L_2)^R=L_1^R L_2^R, then L_1=L_2.

Exercise 6.9 (Concatenation vs union/intersection) Given languages A,B,C\subseteq \Sigma^*. Which of the following equalities are always true?

  1. (A\cup B) C=AC\cup BC and A(B\cup C)=AB\cup AC.

  2. (A\cap B) C=AC\cap BC and A(B\cap C)=AB\cap AC.

6.4 n-th power of a language

For n\in \mathbb{N} at least 1, L^n denotes the language L concatenated with itself n times and L^0=\{\varepsilon\}.

Exercise 6.10 Show that for every n,m\in \mathbb{N}, L^{n+m}=L^nL^m. Show that if we want this property to hold then we must define L^0=\{\varepsilon\}.

Exercise 6.11 Given a language L and a positive integer n, is it true that |L^n|=|L|^n?

6.5 Kleene star

The Kleene star of a language L is the language \begin{align*} L^*&=\bigcup_{n\in \mathbb N}L^n \\ &=L^0\cup L^1\cup L^2\cup \cdots \\ &= \{\varepsilon\}\cup L \cup L^2\cup \cdots\ . \end{align*} It is always the case that \varepsilon\in L^* and L\subseteq L^*. This operation is named after Stephen Cole Kleene, who introduced it in the context of regular expressions.

Stephen Cole Kleene (1909–1994)

Stephen Cole Kleene (1909–1994)

Exercise 6.12 (Clash of notation!? 🌱) Given an alphabet \Sigma, \Sigma itself is also a language and hence we have a clash of notation! \Sigma^* might denote either (1) the Kleene star of the language \Sigma, or (2) the set of all words over \Sigma. This is not a problem because the languages in (1) and (2) coincide. Prove this fact.

Exercise 6.13 For what languages L is L^* infinite and for which ones it is finite?

Exercise 6.14 Prove that \{w\in \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}}\}^* :\textcolor{darkred}{\mathtt{ab}}w=w\textcolor{darkred}{\mathtt{ab}}\}=\{\textcolor{darkred}{\mathtt{ab}}\}^*.

NoteWhy do we care about the Kleene star?

Later in the course we will see that the Kleene star is a very important operation. In particular, it is one of the operations that define the class of regular languages. But, for the moment let’s try to argue why it is a natural operation to consider.

On the real numbers you should be very familiar with the basic operations sum + and product \cdot. The next basic operation on the reals is the exponentiation, \mathrm{e}^x. This function has Taylor expansion

\mathrm{e}^x=1+x+\frac{x^2}{2\phantom{!}}+\frac{x^3}{3!}+\frac{x^4}{4!}+\cdots \ .

On the set of all languages, the union and concatenation behave a lot like a sum and product (see Exercise 6.9), in this context then the Kleene star could be seen as an analogue of the exponentiation. But, please do not take this analogy too literally.

Since the concatenation is not commutative, exponentiation and Kleene star have different algebraic properties. For example, \mathrm{e}^{x+y}=\mathrm{e}^x\cdot \mathrm{e}^y, but in general, (L_1\cup L_2)^*\neq L_1^*\cdot L_2^* (see Exercise 6.15).

Exercise 6.15 (Kleene star vs union)  

  1. (🌱) Give an example of L_1,L_2\subseteq \Sigma^* s.t. (L_1\cup L_2)^*\neq L_1^*\cup L_2^*.
  2. (🌱) Give an example of L_1,L_2\subseteq \Sigma^* s.t. (L_1\cup L_2)^*\neq L_1^*\cdot L_2^*.
  3. Show that for every L_1,L_2\subseteq \Sigma^*, (L_1\cup L_2)^*=L_1^*\cdot(L_2\cdot L_1^*)^*\ .

Exercise 6.16 (Kleen star vs intersection)  

  1. Given languages L_1,L_2\subseteq \Sigma^*, does it hold that L_1^*\cap L_2^*= (L_1\cap L_2)^*?
  2. Does L_1\cap L_2=\emptyset for two languages L_1, L_2 \not=\emptyset imply L_1^*\not=L_2^*?

Exercise 6.17 (Kleene star vs reverse) It is true that (L^*)^R=(L^R)^* for every L? That is, is it true that reverse and Kleene star commute?

Exercise 6.18 (Kleene star vs concatenation) Give an example of languages L_1,L_2\subseteq \Sigma^* s.t. L_1^*L_2^* \neq (L_1L_2)^*.

Exercise 6.19 (Kleene star vs inclusion)  

  1. Show that for every two languages L_1,L_2\subseteq \Sigma^*, if L_1\subseteq L_2 then L_1^*\subseteq L_2^*.
  2. Show that the converse of the previous item does not hold. That is, give two languages L_1,L_2 s.t. L_1^*\subseteq L_2^* but L_1\not\subseteq L_2. What if L_1=\{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}}\} and L_2\subseteq \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}}\}^*, does the converse hold in this special context?
  3. Does it hold for every language L that \overline{L^*}\subseteq \overline{L}\subseteq \overline{L}^*? What if we reverse the inclusions? Does \overline{L^*}\supseteq \overline{L}\supseteq \overline{L}^* always hold?