積構造法（product construction）

假設你想要一台機器同時追蹤「兩件事」——比如「含偶數個 a」與「以 b 結尾」。與其發明一台聰明的單一機器，不如讓兩台小機器並排、同步、在同一段輸入上一起跑，並隨時記下「每一台」目前所在的位置。這對「成對的快照」就是積構造法的核心想法：一台新自動機，其狀態是一對對的狀態，分別來自原本的兩台機器。

形式上，給定同一字母表上的 DFA M1（狀態集 Q1）與 M2（狀態集 Q2），建一台新 DFA，其狀態集是笛卡兒積 Q1 × Q2（所有的對 (p, q)）。起始狀態是兩個起始狀態組成的對。讀到符號 x 時，新機器逐分量移動：從 (p, q) 走到 (δ1(p, x), δ2(q, x))——各半各自遵循自己的轉移函數 δ（delta）。唯一還要決定的是哪些對是「接受」的。當 p 與 q「都」是接受狀態時讓 (p, q) 接受，就辨識交集 L1 ∩ L2；當「任一」是接受狀態時就接受，便辨識聯集 L1 ∪ L2。轉移完全相同，只有接受集不同。

這是正規語言對交集與聯集封閉的標準證明，而且給出實在的上界：若 M1 有 m 個狀態、M2 有 n 個狀態，則積最多有 m·n 個狀態（丟掉無法到達的對後通常更少）。同樣的把戲——讓多台自動機並行、觀察所有分量——在整個理論中一再出現。