Operations on Languages

The second trap: the size of LM can be less than the product. If L is {a, aa} and M is {a, aa}, then LM is {aa, aaa, aaaa}, which has three members, not four, because aa concatenated with a and a concatenated with aa both give aaa.

The third trap: powers are concatenation, not repetition of a single string. L to the 2 is LM with M equal to L, so it is every concatenation of any member with any member, not just each member with itself.

The first line is a definition and it is forced, exactly as w to the 0 being epsilon was forced in chapter 3: it is what makes the law L to the m concatenated with L to the n equals L to the (m plus n) hold when m is zero.

The Kleene closure

So L star is every string that can be split into any number of pieces, each of which is in L, including zero pieces.

The empty string is always in L star, for every L, because zero pieces concatenate to epsilon. That includes the empty language: the closure of the empty language is {epsilon}, which has one member. It is the single most asked trap on this topic.

L plus is L star with epsilon removed, unless epsilon is in L. If epsilon is in L then L plus already contains it, and L plus equals L star. If epsilon is not in L then L plus is L star minus {epsilon}. Stating it as "L plus is L star without epsilon" is wrong in the first case.

L plus equals L concatenated with L star, and also L star concatenated with L. Both are used in chapter 31.

L star star equals L star. Closing something already closed adds nothing, because a string split into pieces each of which splits into pieces of L splits into pieces of L.

Worked computations

Let Sigma be {a, b}, and take

Two things to notice in that table. LM has three members and not four, because a concatenated with b and ab concatenated with epsilon both give ab. And LM is not ML, which the fourth and fifth rows show explicitly.

Now some closures.

The first row is the trap. The second is worth seeing beside it: the closure of {epsilon} is also {epsilon}, because concatenating any number of copies of the empty string gives the empty string.

The operations as machines

Everything above is a definition about sets. Chapter 38 proves that if L and M are regular then so is each of these, by building a machine, and chapter 34 uses three of the constructions to turn a regular expression into a machine. Here is one of them in full, so this chapter is not only definitions.

Union, on two machines. Take a machine for L and a machine for M, and build a new one with a fresh start state having an empty move into each of the two old start states. A run then commits to one machine at the outset and never returns, so the new machine accepts exactly what one or the other accepts.

Accepts: a, b

Rejects: ε, ab, ba, aa, bb

a + b

The two sub machines here accept {a} and {b}, so the union accepts {a, b}, which the claim lists and the comparison confirm.

Substitution, homomorphism, and the reverse of each

The operations above build one language out of two. These build one language out of one, by REPLACING each symbol, and MU has asked for them by name.

Substitution

A substitution replaces every symbol by a whole language. Choose, for each symbol a of Sigma, a language f(a) over some alphabet Delta. Then:

Worked. Let Sigma be {a, b}, Delta be {0, 1}, and:

Notice f(ab) and f(ba). Substitution respects order, because concatenation does.

Homomorphism

A homomorphism is a substitution whose every image is a SINGLE string, so h(w) is one string rather than a language. Writing h(a) for that string:

Worked, with h(a) = 01 and h(b) = 1:

Every homomorphism is a substitution and not the other way round. The f above is not a homomorphism, because f(a) holds two strings.

The reverse, which examinations call reverse substitution

Going forwards replaces symbols by languages. Going backwards asks which strings would have been sent into a language you already have.

For a homomorphism, where h(w) is one string, the definition is exact and is the one to quote:

Worked, with the same h and with M being {0101, 011}:

So the reverse of M under h is {aa, ab}, and every longer string is excluded because h never shortens: a contributes two symbols and b one, so nothing longer than two symbols can land in a set whose longest member has four.

For a substitution, where f(w) is a whole language, the question is what "lands in M" should mean, and the strict reading is the useful one: w counts when EVERYTHING f can make of it is in M.

Worked, with the same f and with N being {0, 01, 011, 0101, 01101}:

So the reverse of N under f is {a, ab}.

Why these operations matter. The regular languages are closed under all four, and so are the context free languages, which chapters 38 and 51 record. An inverse homomorphism is the standard way to turn a question about one alphabet into a question about another, and it is how several closure proofs are written.

Distinctions

What it does NOT mean

L concatenated with the empty language is not L. It is the empty language. The identity for concatenation is {epsilon}.

L star does not exclude epsilon. It always contains it, even when L is empty.

L plus is not always L star minus epsilon. Only when epsilon is not in L.

The complement is not "the other obvious language". It is everything in Sigma star that is not in L, and Sigma must be stated for the question to have an answer.

L to the 2 is not the doubled strings. It is all ordered pairs concatenated, and the last table above shows the difference.

Quick revision

• Union, intersection, difference and complement are the set operations; the complement is with respect to Sigma

star, which must be stated.

• LM is every x from L followed by every y from M. Associative, not commutative.
• {epsilon} is the identity for concatenation; the empty language annihilates.
• L to the 0 is {epsilon}, which is forced by the exponent law.
• L star is any number of pieces from L, including none, so epsilon is always in it, and the closure of the

empty language is {epsilon}.

• L plus is one or more pieces, and equals L star minus {epsilon} only when epsilon is not in L.
• L star star equals L star, and L plus equals L concatenated with L star.
• The size of LM can be smaller than the product of the sizes, because different pairs can give the same

string.

• A substitution replaces each symbol by a LANGUAGE and extends to strings by concatenation and to languages

by union. A homomorphism is the case where each image is one string.

• The reverse of a homomorphism is the set of w whose image lands in the given language. The reverse of a

substitution is the set of w every one of whose images lands in it.

• Every homomorphism is a substitution; the reverse does not hold.

Test yourself

1. Give L M and M L for L = {a, ab} and M = {b, ε}. LM is {ab, a, abb}, which is {a, ab, abb} with three members, because a with b gives ab and ab with epsilon also gives ab. ML is {ba, bab, a, ab}, four members.

2. What is the closure of the empty language, and its size? {epsilon}, of size 1. Zero pieces concatenate to the empty string, and that is the only string obtainable.

3. When does L plus equal L star? Exactly when epsilon is in L, since L plus then already contains the empty string from a single piece.

4. Give the complement of the language of strings over {a, b} that end in a. Every string over {a, b} that does not end in a, that is, epsilon together with every string ending in b. The answer must include epsilon, and it is meaningless without saying that Sigma is {a, b}.

5. For L = {a, b}, give L to the 2 and the set of doubled strings. L to the 2 is {aa, ab, ba, bb}. The doubled strings are {aa, bb}. The two are different, and only the first is what L to the 2 means.

6. Simplify the closure of the closure of L, and the concatenation of L with the empty language. The closure of the closure is the closure. The concatenation with the empty language is the empty language.

7. Define substitution, and give f(ab) for f(a) = {0, 01} and f(b) = {1}. A substitution assigns a language to each symbol, sends epsilon to {epsilon}, sends x a to the concatenation of f(x) with f(a), and sends a language to the union of the images of its members. Here f(ab) is f(a) concatenated with f(b), which is {01, 011}.

8. Define reverse substitution, and reverse {0101, 011} under h, where h(a) = 01 and h(b) = 1. The reverse of a language M under a homomorphism h is the set of strings w with h(w) in M; for a general substitution it is the set of w all of whose images lie in M. Here h(aa) is 0101 and h(ab) is 011, both in M, and no other string qualifies, so the answer is {aa, ab}.

9. Is every substitution a homomorphism? No. A homomorphism is the special case in which every image is a single string. The f of question 7 is not one, because f(a) holds two strings.