set operations

Once you have sets, you want to combine and compare them, and there are a handful of standard ways to do that. Picture two overlapping circles drawn on a page (a Venn diagram). The union grabs everything in either circle, the intersection keeps only the overlap, the difference keeps one circle minus the overlap, and the complement is everything outside a circle. These are the verbs of set theory, and the theory of computation uses them constantly to build new languages out of old ones.

Precisely: the union A ∪ B (the ∪ being the union symbol) is the set of everything that is in A or in B (or both); the intersection A ∩ B (the ∩ being the intersection symbol) is the set of everything in A and in B at the same time; the difference A − B (also written A \ B) is everything in A but not in B; and the complement of A, written A-bar or A^c, is everything in the surrounding universe that is not in A. For example, if the universe is all strings over {a, b} and A is the set of strings starting with a, then the complement of A is the set of strings that do not start with a (which includes the empty string). The empty set is the identity for union (A ∪ ∅ = A) and the absorbing element for intersection (A ∩ ∅ = ∅).

These operations are the foundation of closure properties later on: when we ask 'if L1 and L2 are regular languages, is L1 ∪ L2 also regular?', we are asking whether the class of regular languages is closed under the union operation. Notice that complement only makes sense once you have fixed a universe — 'everything not in A' is meaningless until you say everything out of what. In automata theory that universe is almost always Σ-star, the set of all strings over the alphabet.