7  Closure properties

Given a class of languages \mathcal{C} (over a fixed alphabet \Sigma) and an operation \circ on words in \Sigma^* (say one of the ones defined in Chapter 6), we can ask whether \mathcal{C} is closed under the operation \circ, that is if \circ applied to languages in \mathcal{C} gives a language in \mathcal{C} too.

For example,

• a set of languages \mathcal{C} is closed under union if for every two languages L_1,L_2\in \mathcal{C} it holds that L_1\cup L_2\in \mathcal{C};
• a set of languages \mathcal{C} is closed under homorphisms if for every language L\in \mathcal{C} and every homomorphism \sigma:\Sigma^*\to\Sigma^* it holds that \sigma(L)\in \mathcal{C};
• a set of languages \mathcal{C} is closed under inverse homorphisms if for every language L\in \mathcal{C} and every homomorphism \sigma:\Sigma^*\to\Sigma^* it holds that \sigma^{-1}(L)\in \mathcal{C};
• … similarly, we can define what it means for \mathcal{C} to be closed under any of the operations in Chapter 6.

Exercise 7.1 Show that if a class of languages \mathcal{C} is closed under union, then for every finite set of languages L_1,\dots,L_n\in \mathcal{C}, then L_1\cup \cdots\cup L_n\in \mathcal{C}.

Exercise 7.2 (A common error) Show that Exercise 7.1 in general does not hold when the union instead of being over a finite set is over an infinite set of languages in \mathcal{C}.

7.1 Closure properties of \mathbf{Finite} and \mathbf{co}\mathbf{Finite}

Exercise 7.3 For which of the operations defined in Chapter 6,

1. is the set of languages \mathbf{Finite} closed?
2. is the set of languages \mathbf{co}\mathbf{Finite} closed?

This is the first time we see this type of question, but indeed this will be a constant in this course. An analogous question will exist for all the classes of languages we see in this course (\mathbf{Regular}, \mathbf{CFL},\mathbf{P},\mathbf{NP},\mathbf{R},\mathbf{RE}, \dots).

Exercise 7.4 The set of all languages over \Sigma^* (that is \mathscr{P}(\Sigma^*)) has the following properties

• it contains \emptyset;
• it contains \{\varepsilon\};
• it contains \{\textcolor{darkred}{\mathtt{s}}\} for each symbol \textcolor{darkred}{\mathtt{s}}\in \Sigma;
• it is closed under union;
• it is closed under concatenation.

Show that \mathbf{Finite} is the smallest (w.r.t. inclusion) set of languages with the properties above, that is show that

1. \mathbf{Finite} has the properties above, and
2. every class of languages with the properties above contains \mathbf{Finite}.

What if we take the list of properties from Exercise 7.4 and we also ask for closure under Kleene star? What is the smallest (w.r.t. inclusion) class of languages with such properties? They are called regular languages (\mathbf{Regular}), and they form a surprisingly rich class of languages.

Exercise 7.5 Using the definitions above, show that \mathbf{Regular}\supsetneq \mathbf{Finite}.