問題：一台機器，兩個要求
在上一篇導覽裡，你已經能熟練地為單一模式設計一台 DFA——含偶數個 a 的字串、以 b 結尾的字串、長度為三的倍數的字串。每一次，訣竅都一樣：想清楚你「必須記住」的那一件事，再讓狀態成為所有可能答案的有限清單。但真實的規格很少只有單一條件。一個過濾器可能想要「含偶數個 a」而且「以 b 結尾」的字串。一個編譯器檢查可能想要「以字母開頭」而且「不含連續兩個點」的識別字。兩個要求，一台機器。怎麼辦？
天真的直覺是坐下來發明一台精巧的單一機器，同時盯著兩件事。有時你做得到，但它瑣碎又容易出錯，而且隨著條件越加越多會指數般惡化。有一個遠遠更好的點子，而且簡單到幾乎有點難為情：不要去建一台同時盯兩件事的機器；而是把你「已經會建」的那兩台機器都建出來，然後讓它們在同一台合併後的機器裡同步、亦步亦趨地一起運行。那台合併後的機器，正是乘積構造所產生的東西。
一顆腦袋裡的兩台機器：把狀態配成對
畫面是這樣的。想像你腦中帶著兩座小旋轉閘門。機器 A 追蹤 a 的奇偶性：它有兩個狀態，叫它們「偶」與「奇」，每個 a 都讓它翻面，每個 b 都讓它原地不動。機器 B 追蹤最後一個符號：它有兩個狀態「見A」與「見B」，讀到 a 就跳到「見A」，讀到 b 就跳到「見B」。現在把輸入字串只讀一遍，但把每個符號「同時」餵給「兩台」機器。在每一刻，你完整的心理狀態都是一個配對：（A 在哪裡，B 在哪裡）——例如（偶, 見B）。
那個配對本身，就是一台全新 DFA 的「單一」狀態。若 A 有 2 個狀態、B 有 2 個狀態，合併後的機器最多有 2 乘 2 = 4 個狀態，每個配對各一個：（偶,見A）、（偶,見B）、（奇,見A）、（奇,見B）。這個由所有配對構成的集合，恰好就是 A 的狀態集與 B 的狀態集的笛卡兒積——這也正是整個技巧為何叫做乘積構造。合併後的起始狀態，就是兩台原機器各自起始狀態配成的對；而每一條合併後的轉移，只是讓兩半同時各走自己的一步。
把它精確地建出來
我們把它寫成一份食譜。設 A 的轉移函數是 deltaA、B 的是 deltaB，兩者都建立在同一個字母表 Sigma（希臘大寫字母 Σ，也就是你固定下來的符號集合）上。乘積機器的狀態是所有配對 (p, q)。它在讀到符號 x 時的轉移，是逐分量定義的：delta((p, q), x) = (deltaA(p, x), deltaB(q, x))——A 的那部分依 A 的規則移動，B 的那部分依 B 的規則移動，兩者讀的都是同一個 x。這短短一行，就是整台引擎。
到目前為止的一切，無論你想要哪個邏輯連接詞都一模一樣。唯一改變的，是你宣告「哪些配對」是接受狀態。想要 A「而且」B（兩個語言的交集）？就在「p 在 A 中接受『而且』q 在 B 中接受」時，接受配對 (p, q)。想要 A「或」B（聯集）？就在「p 在 A 中接受『或』q 在 B 中接受」時接受。想要「在 A 中但不在 B 中」（集合差）？就在「p 接受但 q 不接受」時接受。機械是一樣的；你只是在兩個分量的判決之上，挑一條規則。
A: even number of a's B: ends in b (start = SawA, accepts SawB)
states {Even, Odd} states {SawA, SawB}
on a: flip on b: stay on a: -> SawA on b: -> SawB
PRODUCT for "even a's AND ends in b" (start = (Even, SawA))
state on a on b accept? (AND)
--------------- ----------------- ----------------- ----------------
(Even, SawA) (Odd, SawA) (Even, SawB) no (not ends-b)
(Even, SawB) (Odd, SawA) (Even, SawB) YES (even & ends-b)
(Odd, SawA) (Even, SawA) (Odd, SawB) no (odd a's)
(Odd, SawB) (Even, SawA) (Odd, SawB) no (odd a's)
trace "abab": (Even,SawA) -a-> (Odd,SawA) -b-> (Odd,SawB)
-a-> (Even,SawA) -b-> (Even,SawB) => accept (1 of 4 states)更深的回報：封閉性質
退一步，注意你其實「證明」了什麼。若 A 識別一個正規語言 L1、B 識別一個正規語言 L2，那麼乘積機器就是一台貨真價實、有限的 DFA，它識別兩者的交集（或聯集、或差）。所以兩個正規語言的交集「本身」也是正規的——它逃不出這個家族。同樣的構造，換一條接受規則，也說明聯集同樣是正規的。這些保證叫做正規語言的封閉性質：這個家族在交集與聯集之下是封閉的，意思是你永遠無法靠組合兩個成員而離開它。
補集更簡單，根本不需要乘積。給定一台識別 L 的 DFA，只要把每個狀態的判決翻面：每個接受狀態變成不接受，反之亦然。新機器恰好接受舊機器所拒絕的那些字串，所以正規語言的補集仍是正規的。這就是補集構造，而它能行得通「正是因為」DFA 是全函數且確定型的——對每個字串它都恰好落在唯一一個明確的狀態，於是「被拒」與「被接受」乾淨地把所有字串分成兩半，沒有縫隙。
乘積能買到什麼、不能買到什麼
對代價要誠實。把一台 m 個狀態的機器與一台 n 個狀態的機器組合，最多得到 m 乘 n 個配對狀態——數量是「相乘」的。兩個各 5 狀態的條件給出 25 個；串四個下去，就逼近 600 了。這個膨脹是在「狀態數」上，而不是在執行時間上：你仍然只讀輸入一次、每個符號走一步，所以乘積 DFA 判定成員資格的時間與輸入長度成正比，和任何 DFA 一樣。乘積執行起來便宜，只有寫下來才昂貴。
而這裡是你必須尊重的界線。乘積讓你組合那些「各自本來就已經是正規」的條件，它不會、也不能賦予 DFA 額外的計數能力。你可以把「偶數個 a」和「偶數個 b」取交集——兩者都正規，所以交集也正規。但你「不能」用乘積去建一台識別「a 的個數等於 b 的個數」的 DFA，因為那不是有限記憶條件的組合；它要求記住一個無上限的計數，而這會直撞任何 DFA 的有限記憶極限。乘積是在正規世界「內部」組合的方法，而絕非衝出正規世界的途徑——而 DFA 為什麼永遠無法無上限地計數，正是下一篇導覽的主題。