集合運算（set operations）

一旦有了集合，你就會想把它們組合、比較，而做這件事有幾種標準的方法。想像在紙上畫兩個相交的圓圈（范氏圖）。聯集把任一圈裡的東西全部抓進來，交集只留下重疊的部分，差集留下某一圈扣掉重疊，補集則是某一圈以外的一切。這些是集合論的動詞，而計算理論不斷用它們從舊語言造出新語言。

精確地說：聯集 A ∪ B（∪ 是聯集符號）是所有在 A 裡或在 B 裡（或兩者都在）的東西構成的集合；交集 A ∩ B（∩ 是交集符號）是所有同時在 A 又在 B 裡的東西；差集 A − B（也寫成 A \ B）是在 A 裡但不在 B 裡的一切；A 的補集，寫成 A 上加一橫或 A^c，是周圍宇宙中所有不在 A 裡的東西。舉例來說，如果宇宙是 {a, b} 上所有字串，A 是以 a 開頭的字串集合，那麼 A 的補集就是不以 a 開頭的字串集合（其中包含空字串）。空集合是聯集的單位元素（A ∪ ∅ = A），也是交集的吸收元素（A ∩ ∅ = ∅）。

這些運算是後面封閉性的基礎：當我們問「如果 L1 和 L2 都是正規語言，L1 ∪ L2 是否也是正規語言？」時，問的就是正規語言這個類別是否對聯集運算封閉。請注意，補集只有在固定了一個宇宙之後才有意義——「所有不在 A 裡的東西」在你說清楚「在什麼之外」之前是沒有意義的。在自動機理論裡，這個宇宙幾乎總是 Σ*（讀作 Sigma-star），也就是字母表上所有字串的集合。