Why these languages are closed under union or concatenation?

Question

This is a question in my text book that I cannot understand the solution provided for that:

In each case below, give a simple descreption of the smallest set of languages that contains all the "basic" languages $\varnothing$,$\{\Lambda\}$, and $\{\sigma\}$ (for every $\sigma \in \Sigma$) and is closed under the specefied operation.

1. Union
2. Concatenation
3. Union and Concatentation

Here are my questions about the above excersise:

• What is the meaning of

smallest set of languages that contains all the "basic" languages $\varnothing$,$\{\Lambda\}$, and $\{\sigma\}$ (for every $\sigma \in \Sigma$)

In other words, What are the sets that I should find for the answers?

• The solution manual suggested "Every zero or one member subset of $\{x | x\in\Sigma^*\}$" for closure under concatenation

I don't understand why it is closed under union? suppose $\{\sigma_1\}$. Is $\sigma_1\sigma_1$ closed under that? No.

Answer 1

We have sets in different levels here: sets of words (languages) and sets of languages. To avoid confusion I will call the latter a "family" of languages.

A family of languages $\mathcal F$ is closed under an (binary) operation $\star$ if for we apply $\star$ to any pair of languages $K,L\in \mathcal F$ also the result $K\star L$ is in $\mathcal F$.

If we start with a set of languages and some operations, then finding the closure of those languages under the given operations ("the smallest family closed under") is equivalent to finding which languages can be build from the starting set using the operations.

In your question we start with "basic" languages, $\varnothing$, $\{\Lambda\}$, $\{a\}$, $\{b\}$ when $\Sigma =\{a,b\}$, and three possible sets of operations.

The answer form the manual you quote is for the operation concatenation (item 2). Using concatenation I can build new languages from the basic ones: $\{a\}\cdot\{a\} =\{aa\}$, and then we can repeat $\{aa\}\cdot\{b\} =\{aab\}$. And so on.

The observation here is that in this way we always build singleton languages, i.e., consisting of a single word. Also all singleton languages over the alphabet can be obtained by repeated concatenation.

One point of possible confusion is that the family of languages is closed under concatenation, not each of the resulting languages. So when $L=\{a\}$ and $L \in \mathcal F$ we have $L\cdot L \in \mathcal F$ so $\{aa\} \in \mathcal F$ but not $a\cdot a \in L$.