DFA 等價問題（the DFA equivalence problem）
假設有人給你兩台看起來不同的有限自動機——狀態不同、接線不同——並問你：它們其實是否識別『完全相同』的語言？這就是等價問題，EQ_DFA = {(A, B) : A 與 B 是 DFA 且它們識別相同語言}。聽起來你似乎得在無窮多個字串上比較它們的行為，但有個優雅的辦法，把它化約成單一一次空語言測試。
關鍵想法是對稱差。兩個集合相等，恰好等於「沒有任何東西屬於其中之一卻不屬於另一個」——也就是它們的對稱差（被 A 接受但不被 B 接受的字串，連同被 B 接受但不被 A 接受的字串）為空。兩個正規語言的對稱差本身也是正規的，而你可以用乘積構造法搭配取補集直接造出它的 DFA C：C =（A ∩ 非 B）∪（非 A ∩ B）。構造 C 是一件有限的、機械式的工作。接著，A 與 B 等價，若且唯若 C 的語言為空，這用 DFA 空語言程序（一次有限的可達性搜尋）即可了結。恰好在 C 的語言為空時，把 (A, B) 接受進 EQ_DFA。
所以 EQ_DFA 是『可判定』的——有限自動機的等價性在演算法上很溫馴。這很重要，因為它意味著你可以機械地驗證兩個有限狀態設計（兩個正規表示式引擎、兩個電路、兩份協定規格）在所有輸入上行為完全相同，這是更豐富的模型辦不到的事。對比很鮮明、值得標記：等價性對 DFA 可判定，但對上下文無關文法與圖靈機卻『不可判定』。是有限的記憶讓相等性可檢查；一旦模型能用無界的記憶，比較兩者是否相等就滑出了可及範圍。
要檢查 A 與 B 是否在所有輸入上一致，造出一台 C，恰好接受那些「它們意見不同」的字串（在 A 中且不在 B 中，或在 B 中且不在 A 中）。對 C 跑空語言測試：若 C 的語言為空，沒有任何字串能區分它們，於是它們等價；若有某個字串能到達 C 的接受狀態，那個字串就是一個具體的反例。
語言相等 = 它們對稱差為空——一個有限、可判定的檢查。
等價性對 DFA 可判定，但對 CFG 與圖靈機『不可判定』。化約成一次空語言測試之所以可行，僅僅因為有限自動機的記憶是有限的。