JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Closure Properties: Building New Languages

You can already build a DFA, an NFA, and a regular expression — three faces of one family. This guide hands you a workshop: take regular languages you already trust and combine them (union, intersection, complement, star, reversal) with the guarantee that the result is still regular. Each combination comes with an explicit machine you can build, and the same toolbox doubles as a sneaky way to prove a language is NOT regular.

A toolbox that never leaks

Picture a box of LEGO bricks with a quiet promise: anything you build out of these bricks still fits back inside the same box. The regular languages behave exactly like that box. Take any regular languages, snap them together in certain standard ways, and the result is STILL regular — it never escapes the family. We say the regular languages are closed under those operations, and this is the closure property that lets us assemble complicated recognizers out of simple, trustworthy ones.

Here is the headline list. If L and M are regular, then so are: their union (strings in either one), their intersection (strings in both), the complement of L (every string over the alphabet NOT in L), the concatenation LM (an L-string glued in front of an M-string), the Kleene star L* (zero or more L-strings glued together), and the reversal of L (every string spelled backwards). Each claim is proved not by hand-waving but by an explicit construction: a recipe that takes the automata or regular expressions you already have and mechanically builds one for the result. The rest of this guide walks through those recipes one machine at a time.

Two machines at once: the product construction

Suppose you want one machine that tracks TWO things at once — say 'has an even number of a's' AND 'ends in b'. Instead of inventing a clever single automaton, run both small machines side by side, in lockstep, on the same input, and keep a snapshot of where EACH one currently is. That paired snapshot is the whole idea of the product construction: a new DFA whose states are PAIRS of states, one drawn from each original machine.

Formally, given DFAs M1 (states Q1) and M2 (states Q2) over the same alphabet, build a DFA whose states are the pairs (p, q) — the Cartesian product Q1 × Q2. The start state is the pair of start states. On reading a symbol x the pair moves component by component: from (p, q) it goes to (delta1(p, x), delta2(q, x)), where each delta is just that machine's own transition function. The transitions are now completely fixed; the ONLY remaining choice is which pairs accept. Mark (p, q) accepting when BOTH halves accept, and you recognize the intersection. Mark it accepting when EITHER half accepts, and you recognize the union. Same wiring, different lights.

M1 = even number of a's        M2 = ends in b
states {E, O}                  states {notB, seenB}
 start E (accept)               start notB (reject)
  E --a--> O   E --b--> E         notB --a--> notB   notB --b--> seenB
  O --a--> E   O --b--> O         seenB --a--> notB  seenB --b--> seenB

PRODUCT  (4 paired states, run both at once):
  state      on a ->        on b ->
  (E,notB)   (O,notB)       (E,seenB)
  (E,seenB)  (O,notB)       (E,seenB)
  (O,notB)   (E,notB)       (O,seenB)
  (O,seenB)  (E,notB)       (O,seenB)
  start = (E,notB)

  INTERSECTION  accept only (E,seenB)   <- even a's AND ends in b
  UNION         accept any pair with E first OR seenB second
One DFA, four paired states, tracking both conditions in parallel; only the accept set decides union versus intersection.

This single construction proves closure under intersection AND union, and it even hands you a size bound: if M1 has m states and M2 has n states, the product has at most m·n states — usually fewer once you throw away pairs no input can reach. Notice the contrast with the previous rung: there, nondeterminism gave conciseness but the subset-construction blowup could be exponential. Here, running two DETERMINISTIC machines in parallel costs only the PRODUCT of their sizes, which stays modest. The same parallel-tracking trick — watch every component at once — will return again and again as you climb.

Flipping the lights: complement

If you have a machine that says YES to exactly the strings you want, how do you get one that says YES to all the OTHER strings? For a DFA the answer is delightfully cheap: flip every light. Everywhere the machine used to accept, make it reject; everywhere it used to reject, make it accept. The states, the arrows, the start state — all untouched. That is the entire complement construction: swap the accept set for its opposite (the new accept set is Q minus the old F), and the machine now recognizes the complement, every string over Sigma that the original rejected.

Why is flipping enough? Because a DFA is TOTAL and DETERMINISTIC: on any input it follows exactly one path to exactly one final state, which is either accepting or not. So 'M accepts w' and 'the flipped M accepts w' are exact opposites, string by string — precisely the complement. The example is tiny: a two-state DFA for 'even number of a's' accepts in E and rejects in O; swap them and O accepts, E rejects, giving 'odd number of a's' with the very same arrows.

Gluing and reversing: star, concatenation, reversal

Complement and product both happily stayed deterministic, but the gluing operations are far easier to argue if you let yourself slip back into nondeterminism — and you may, because the previous rung proved every NFA can be flattened back to a DFA anyway. For concatenation LM, take the machines for L and M and stitch them: add an epsilon-transition from each accept state of L's machine to the start of M's machine, then let only M's accept states accept. Intuitively, the combined machine reads an L-string, then silently jumps over and reads an M-string. The Kleene star L* is the same trick turned into a loop.

  1. For L*: start from the NFA for L. Add a brand-new start state that is also accepting (because L* always contains the empty string epsilon, the zero-copies case).
  2. Add an epsilon-transition from the new start into the old start, so the machine can optionally begin reading one copy of an L-string.
  3. From every accept state of the L-machine, add an epsilon-transition back to the old start state — this is the loop that lets you read another copy, and another, with no limit.
  4. The result is an NFA recognizing L*; convert it back to a DFA with the subset construction if you want a deterministic machine. Concatenation is the same minus the loop-back and minus the accepting new start.

Reversal is charming. To recognize the reversal of L (every accepted string spelled backwards), take L's automaton and literally run it backwards: reverse the direction of every arrow, make the old start state the new accept state, and add a new start state with epsilon-moves into all the old accept states. Reversing the arrows can introduce forks, so the result is naturally an NFA — which is fine, since NFAs and DFAs recognize the same languages. All three of these gluing constructions are why writing out a regular expression works at all: union, concatenation, and star are exactly the regex operators, and Kleene's theorem (from the regex rung) is the grand statement that these constructions together capture precisely the regular languages.

The same toolbox, used in reverse: closure as a weapon

Here is the twist that makes closure properties more than a convenience. The very fact that regular languages stay regular under these operations is also a way to PROVE a language is NOT regular — without touching the next guide's pumping lemma at all. The move is a kind of logical judo, called closure as a proof tool: assume your suspect language IS regular, combine it with known-regular ingredients using operations that preserve regularity, and if that legal combination lands on a language you ALREADY know is not regular, you have a contradiction — so the suspect was never regular.

A worked example makes it concrete. Claim: L = strings over {a, b} with equally many a's and b's is not regular. Suppose, for contradiction, that it were. The language a* b* (all a's, then all b's) is plainly regular. Since regular languages are closed under intersection, L intersected with a* b* would also be regular. But that intersection is exactly { a^n b^n : n at least 0 } — the famous language a^n b^n. If you already trust that a^n b^n is not regular (the next guides prove it cold), then this is a contradiction: a regular language cannot equal a non-regular one. So the only assumption we made, 'L is regular', must be false.

Closure under homomorphism — a fixed find-and-replace on symbols, where each letter is swapped for a fixed string — gives yet another angle: if applying or un-applying a homomorphism to your candidate would manufacture a known non-regular language, the candidate cannot be regular either. Together with intersection, complement, and reversal, these give you several independent attack routes, so a language that shrugs off one closure argument may collapse under another.

Be honest about the direction of this tool. A closure argument can prove a language is NON-regular, but it can never certify that a single given language IS regular — closure under an operation says nothing about one isolated language standing alone. And the contradiction is only as solid as your base fact: it rests on already knowing that something like a^n b^n is non-regular, which itself must be earned by the pumping lemma or the Myhill-Nerode theorem in the guides ahead.

What you can now do, and where it points

Step back and count what this guide bought you. You can now design by composition: recognize 'valid identifiers' and 'reserved keywords' separately, then take a DIFFERENCE (intersection with a complement) to recognize 'identifiers that are not keywords', knowing for certain that a single finite automaton still exists for the result. You have explicit recipes — product for union and intersection, light-flipping for complement, epsilon-stitching for concatenation and star, arrow-reversal for reversal — and you understand WHY each one preserves regularity rather than merely memorizing that it does.

But notice the boundary did not move. Closure tells you how to STAY inside the regular family; it cannot smuggle a^n b^n in, because no finite combination of regular pieces ever escapes the family, and a^n b^n was never in it. That wall — the finite-memory limit you met two rungs ago — is exactly what the rest of this rung studies head on. The next guide turns the pigeonhole principle into the pumping lemma, a clean test for the unavoidable looping that finite memory forces; the guide after that turns it into a recipe for proving non-regularity; and the closing guides hand you the sharper, exact tool (Myhill-Nerode) and the unique smallest machine (DFA minimization). The closure toolbox you just built is both your construction kit and your first proof weapon for everything that follows.