語言運算（language operations）

既然語言只是一個字串集合，我們就能用組合與變換任何集合的相同方式來組合與變換語言，再加上幾個專屬於字串的運算。把它想成「用舊賓客名單做出新名單」的食譜：把兩份名單合併、只保留兩份都有的名字、列出所有沒被邀請的人，或把名單黏在一起。每個運算取一或兩個語言，產生一個新的語言。

集合式的運算有：聯集 L 聯集 M（在 L 或 M 中的所有字串，寫作 L ∪ M）、交集 L 交集 M（兩者都在的所有字串，寫作 L ∩ M），以及補集（Σ 上所有不在 L 中的字串，寫作 L 上加一橫或 Σ* 減 L）。字串式的運算有：串接 L . M（L 的每個字串後面接 M 的每個字串，即 { xy : x 在 L、y 在 M }）與 Kleene 星號 L*（把 L 中任意數量的字串串接起來，包括零個，所以 L* 永遠含 ε）。例如，若 L = {a}、M = {b}，則 L . M = {ab}、L ∪ M = {a, b}、L* = {ε, a, aa, aaa, ...}。

這些運算是整門理論的動詞。一個核心而優美的問題是：哪些語言家族對哪些運算封閉，意思是運算結果仍留在同一個家族裡。例如正規語言對聯集、交集、補集、串接與 Kleene 星號都封閉，而這種封閉性本身就是強大的證明工具：若你能只用這些運算把一個語言由正規的零件組裝起來，結果就自動是正規的。不過要小心，封閉性對每個家族並非理所當然：上下文無關語言對聯集封閉，但對交集或補集不封閉，所以未經檢查不能假設某運算會保持某性質。