language operations

Since a language is just a set of strings, we can combine and transform languages the same way we combine and transform any sets, plus a couple of operations that are special to strings. Think of it like recipes for making new guest lists out of old ones: merge two lists, keep only the names on both, list everyone not invited, or glue lists together. Each operation takes one or two languages and produces a new language.

The set-style operations are: union L union M (all strings in L or in M, written L ∪ M), intersection L intersect M (all strings in both, written L ∩ M), and complement (all strings over Σ that are NOT in L, written L-bar or Σ* minus L). The string-style operations are: concatenation L . M (every string of L followed by every string of M, that is { xy : x in L, y in M }) and the Kleene star L* (any number of strings from L concatenated together, including zero of them, so L* always contains ε). For example, if L = {a} and M = {b}, then L . M = {ab}, L ∪ M = {a, b}, and L* = {ε, a, aa, aaa, ...}.

These operations are the verbs of the whole theory. A central and beautiful question is which families of languages are closed under which operations, meaning the result stays in the same family. The regular languages, for instance, are closed under union, intersection, complement, concatenation, and Kleene star, and this closure is itself a powerful proof tool: if you can build a language from regular pieces using only these operations, the result is automatically regular. Be careful, though, that closure is not automatic for every family: the context-free languages are closed under union but NOT under intersection or complement, so you cannot assume an operation preserves a property without checking.