Why combine languages at all?
From the previous guide you already know that a language is nothing more exotic than a set of strings over some alphabet Sigma (the Greek letter Σ, our fixed pool of allowed symbols). That single idea is powerful precisely because it lets us reuse everything we know about sets. If a language is a set, then we can take two languages and glue them together, overlap them, or stack them — the same way we union and intersect ordinary sets. These combinations are called operations on languages, and they are how we describe big, complicated languages by assembling them from small, simple ones.
Think of it like cooking. You do not write a recipe by listing every molecule; you describe a dish in terms of a few ingredients and a few actions (chop, mix, bake). Operations on languages are those actions. Three of them are the workhorses: union, concatenation, and the Kleene star. The first two come straight from set theory and string-gluing, which you have already met. The third is the genuinely new idea of this guide, and it is the one that quietly unlocks infinity.
The three workhorse operations
Fix two languages L and M over the same alphabet. Their union, written L ∪ M, is simply every string that is in L or in M (or both) — the ordinary set union, no surprises. Their intersection L ∩ M is the strings in both. These behave exactly like the set operations you already know, because languages really are sets. The only thing to remember is that the elements being unioned are strings, not numbers.
Concatenation of languages is more interesting. The concatenation L · M is the set of every string you can form by taking one string from L, one string from M, and gluing them in that order: L · M = { x y : x is in L and y is in M }. So if L = {a, ab} and M = {c, dd}, then L · M = {ac, add, abc, abdd}. Notice we pair each x with each y — four results from two times two choices. Concatenation of languages is just concatenation of strings, lifted to whole sets.
The Kleene star: naming infinity
Concatenation glues two languages once. But what if we want to glue a language to itself, any number of times — zero, once, twice, a hundred times? That is the Kleene star, written with a single star, L*. Read it as 'zero or more strings from L, concatenated together'. Formally, L* is the union of L concatenated with itself k times, for every k starting at 0. The k = 0 case is special and deliberate: concatenating nothing gives you the empty string, so epsilon is always in L*, no matter what L is.
L = { ab }
L^0 = { epsilon } (glue zero copies)
L^1 = { ab }
L^2 = { abab }
L^3 = { ababab }
...
L* = L^0 U L^1 U L^2 U ... = { epsilon, ab, abab, ababab, ... }
L+ = L^1 U L^2 U L^3 U ... = { ab, abab, ababab, ... } (one or more; drops epsilon)Two things deserve emphasis. First, even if L is finite, L* is usually infinite — {ab}* already contains infinitely many strings. A finite description naming an infinite set: that is the whole magic, and it is why automata, which are finite machines, can recognize infinite languages. Second, there is a close cousin, the plus operator L+, which means 'one or more' instead of 'zero or more'. The only difference is whether epsilon is included: L* = L+ ∪ {epsilon}. If epsilon happens to be in L already, then L* and L+ are equal.
Worked example and a few honest cautions
Let us build something real with the toolkit. Take Sigma = {a, b}. Suppose we want the language of all strings that start with a single a and then have any number of b's: a, ab, abb, abbb, and so on. We can name it precisely as {a} · {b}*. Read left to right: one a, glued to zero-or-more b's. The {b}* part contributes epsilon, b, bb, bbb, ...; concatenating an a on the front of each gives exactly a, ab, abb, abbb, .... No 'and so on' hand-waving — the star did the infinite work for us, finitely.
- Start from atomic languages: {a} (one string) and {b} (one string).
- Apply the star to {b} to get {b}* = {epsilon, b, bb, bbb, ...} — now infinite.
- Concatenate {a} on the front: {a} · {b}* pairs the lone a with each of those strings.
- The result is exactly {a, ab, abb, abbb, ...}, described by a finite expression.
A few honesties before we move on. The order of arguments to concatenation matters: L · M is generally not M · L, just as 'ab' is not 'ba'. The star is not optional decoration — L* with no copies still gives you epsilon, so a starred language is never empty. And do not confuse 'infinite' with 'complicated': {b}* is infinite yet utterly simple. Conversely, a regular language need not be infinite; {a, b} is regular and has exactly two strings. Regular does not mean infinite, and infinite does not mean irregular.
Why this toolkit is the foundation of everything ahead
Union, concatenation, and the star are not just convenient — they are the exact building blocks of regular expressions and the regular languages, the very first rung of the Chomsky hierarchy you will climb. Later you will see a beautiful fact: a language can be named by these three operations if and only if a finite automaton can recognize it. So mastering operations on languages now is mastering the grammar of the simplest machines you will ever build.
There is also a deeper reason to care. Recall the idea that a problem can be encoded as a language: a yes/no question becomes 'is this input string in the language of yes-instances?'. Once a problem is a language, asking a computer to solve it becomes the membership problem — does a given string belong to a given language? Operations on languages are then operations on problems: combining, restricting, and transforming the very questions we ask machines to answer. Build these tools into reflex, and the rest of the subject reads like sentences in a language you already speak.