笛卡兒積（Cartesian product）
/ kar-TEE-zhuhn /
兩個集合 A 與 B 的笛卡兒積，是你從 A 取一個元素、從 B 取一個元素所能組成的所有有序對構成的集合。想像一個方格表：A 標示列，B 標示行，方格表的每一格就是一個對。西洋棋盤就是一個小小的笛卡兒積——直線 {a,…,h} 與橫列 {1,…,8} 交叉出 64 格，每一格都用一個（直線, 橫列）對來命名，例如 (e, 4)。和集合不同，對是有序的：(e, 4) 與 (4, e) 是不同的東西。
我們寫成 A × B = {(x, y) : x ∈ A 且 y ∈ B}，其中 (x, y) 是有序對（第一坐標 x、第二坐標 y）。若 A = {0, 1}、B = {a, b, c}，則 A × B 有 2 × 3 = 6 個對：(0,a)、(0,b)、(0,c)、(1,a)、(1,b)、(1,c)。一般而言大小是相乘的：|A × B| = |A| × |B|，這正是「積」這個名字的由來。你可以把它推廣到三個或更多集合，得到有序三元組與更長的元組，這也是為什麼自動機的形式定義會被打包成一個元組。
這個運算在理論裡無所不在。DFA 的轉移函數把一個（狀態, 符號）對送到下一個狀態，所以它的定義域是笛卡兒積（狀態集合）×（字母表）。用來證明正規語言對交集封閉的乘積構造法，同時跑兩台自動機，做法就是把它的狀態集合設為兩個原始狀態集合的笛卡兒積——一個狀態對記住每台機器各自走到哪裡。而下一個要講的關係，其實就是某個笛卡兒積的子集。
若 Q = {q0, q1} 是某 DFA 的狀態、Σ = {a, b} 是它的字母表，則 Q × Σ = {(q0,a), (q0,b), (q1,a), (q1,b)}——這正是轉移函數 δ（delta）必須回答的四個（狀態, 符號）輸入。
DFA 轉移函數的定義域，就是狀態與字母表的笛卡兒積。
對是有序的，積一般不可交換：A × B 與 B × A 含有不同的對（除非 A = B）。別把有序對 (a, b) 和雙元素集合 {a, b} 搞混。