動機
改變字母表可能揭示或隱藏語言的結構。同態把每個輸入符號替換為一個固定的字(可以是空字串),並透過連接把這種替換擴展到整個字。正則語言在正像與逆像下都保持正則,但這兩種構造的方向不同。
對於逆像,DFA 可以對每個輸入符號模擬其整個替換字。對於正像,每條舊轉移被替換為一條拼出其輸出字的路徑;空替換自然變成 ε 轉移。兩種構造都是可有效實現的,並且都明確處理了被擦除的符號。
定義
設 Σ 與 Γ 為有限字母表。幺半群同態 h:Σ∗→Γ∗ 由對每個 a∈Σ 指定的字 h(a)∈Γ∗ 確定,並且 h(ε)=ε,h(uv)=h(u)h(v)。若一個符號的像是 ε,則稱該符號被擦除。
對 L⊆Σ∗,正像為 h(L)={h(w):w∈L}。對 K⊆Γ∗,逆像為 h−1(K)={w∈Σ∗:h(w)∈K}。這是作用於不同字母表上語言的兩種不同運算。
DFA M=(Q,Γ,δ,q0,F) 在字上具有擴展轉移函數 δ∗。ε-NFA 可以走標記為 ε 的轉移而不消耗任何輸入符號。兩者都是有限自動機;ε-NFA 可以透過 ε 閉包與子集構造進行確定化。
若 K⊆Γ∗ 是正則的,則 h−1(K) 是正則的。給定 K 的一個 n 狀態 DFA,透過在一次輸入轉移上模擬各替換字,可得到逆像的一個 n 狀態 DFA。
若 L⊆Σ∗ 是正則的,則 h(L) 是正則的。給定 L 的一個有限自動機以及有限多個字 h(a),可以有效地構造出 h(L) 的一個 ε-NFA。
證明:基於分塊模擬的逆像
設 M=(Q,Γ,δ,q0,F) 接受 K。構造一個 DFA,其狀態集、起始狀態和接受狀態集與 M 相同,但字母表為 Σ,轉移為
δ′(q,a)=δ∗(q,h(a)).若 h(a)=ε,則該轉移使狀態保持不變。對於字 w=a1⋯at,對 t 做歸納可得
δ′∗(q0,w)=δ∗(q0,h(a1)⋯h(at))=δ∗(q0,h(w)).因此新機器接受 w 當且僅當 h(w)∈K,這正是 h−1(K) 的定義。它與原機器有相同的 n 個狀態,不過還可以進一步最小化。這張有限轉移表可以這樣算出:從每個原狀態出發,模擬每個顯式給定的像字。
證明透視
一個輸入符號可以模擬整個字
逆像機器讀入一個符號 a,但在內部讓原 DFA 依次經過 h(a) 的每個符號。若像為空,則不沿任何原轉移前進,狀態保持不變。
關鍵一步是把 ∣h(a)∣ 個原來的步驟打包成一個新步驟。對 t 的歸納用到 δ∗(q,uv)=δ∗(δ∗(q,u),v),其中 u=h(a1⋯at−1),v=h(at),這正是用到 h(uv)=h(u)h(v) 的地方。DFA 必須是完全的,這樣 δ∗(q,h(a)) 對每個狀態和符號才有定義。空像不需要另行處理,因為 δ∗(q,ε)=q。
證明:以替換轉移得到的正像
設 L 的某個 NFA 有一條轉移 qar。若 h(a)=γ1⋯γℓ 且 ℓ≥1,則把該轉移替換為從 q 到 r 的一條路徑,其標記依次為 γ1,…,γℓ,並使用專屬於該轉移的全新中間狀態。若 h(a)=ε,則把它替換為從 q 到 r 的一條 ε 轉移。保留原來的起始狀態與接受狀態。已有的 ε 轉移(如果有的話)仍為 ε 轉移。
原自動機在 w 上的一次接受運行,把每條轉移展開為其替換路徑後,就成為在 h(w) 上的一次運行。反過來,新自動機中的每次運行都可以分解為若干完整的替換路徑和舊的 ε 轉移:全新的中間狀態只有屬於其所在路徑的後繼。對每條完整路徑或擦除邊選擇一條對應的原轉移;若相同的新邊被合併,任選一條對應的原轉移即可。把這些選擇收縮回去,便得到原自動機在某個字 w 上的一次運行,而新運行所消耗的標記為 h(w)。因此新自動機恰好接受 h(L)。
該構造是有限的。像長為 ℓ≥1 的一條轉移會增加 ℓ−1 個中間狀態;被擦除的轉移不增加狀態,只變成 ε 轉移。總規模以各轉移上顯式給定的替換長度之和,加上舊的狀態與轉移為界。對所得 ε-NFA 進行確定化是可行的,但可能使狀態數增加。
證明透視
為甚麼新自動機的運行可以收縮
展開的方向是例行的;論證的重點在反方向。新自動機的運行只能經由某條替換路徑的第一條邊進入全新的中間狀態,進入之後只有唯一的繼續方式,所以在路徑走完之前不能離開它。因此每次運行都分解為完整的替換路徑與舊的 ε 邊,每一段對應一條原轉移。兩項假設是關鍵:中間狀態是全新的,並且每個字 h(a) 都是有限的,所以加入的中間狀態只有有限多個。當 ∣h(a)∣≤1 時不出現中間狀態,分解是顯然的。
例題詳解
設 L=(01)∗,且 h(0)=ab,h(1)=ε。每次出現的 01 映為 ab,所以 h(L)=(ab)∗。在轉移構造中,標記為 0 的轉移變成先讀 a 再讀 b 的路徑,標記為 1 的轉移變成 ε 轉移。
設 K 為 {a} 上偶數長度字構成的語言,且 h(0)=a,h(1)=aa。一個字的像長為偶數,恰當它含有偶數個 0 符號;每個 1 貢獻兩個字母,不影響奇偶性。逆像 DFA 在讀到 0 時改變奇偶狀態,讀到 1 時保持在同一狀態。
若 h(a)=ε,則 a 的逆像轉移在每個狀態 q 上都是 δ∗(q,ε)=q。讀入一個被擦除的輸入符號,不可能改變所模擬的輸出前綴是否被接受。
若 h(a)=h(b)=x,則不同的源字 a 與 b 都映為 x。正像是一個集合,所以 x 只出現一次。所構造的 NFA 對 x 可能有兩條接受運行;非確定性接受只要求至少有一條,而不是恰有一條。
常見錯誤
反例模式
像一般不與補集交換
設 Σ={a},L={ε},且 h(a)=ε。則 h(L)={ε},而 h(Σ∗∖L)={ε} 也成立。這兩個像相交,所以補集的像一般不是像的補集。
當補集所在的全集已指定時,逆像與補集是可交換的:h−1(Γ∗∖K)=Σ∗∖h−1(K)。這只需檢查 h(w) 是否屬於 K 即可得到。它與上面失敗的正像等式是不同的命題。
同態可以擦除符號。若假定每個像都有正長度,就會遺漏有效的情形;若把被擦除的轉移當作消耗一個普通符號,則會識別出錯誤的語言。
集合 h−1(K) 對每個同態都有定義,即使 h 沒有逆映射;而且這兩種運算並不互相抵消。取 h(a)=h(b)=x 與 L={a},則 h(L)={x},但 h−1(h(L))={a,b}=L。一般而言 L⊆h−1(h(L)),並且 h(h−1(K))=K∩h(Σ∗):落在 h 的值域之外的目標字沒有原像。
藉表達式求正像
當源語言由正則表達式給出時,正像的封閉性還有另一種證明。把表達式中的每個源符號 a 替換為拼出 h(a) 的字面表達式,像為空時用 ε。並集、連接、星號、∅ 與 ε 保持不動。
關鍵等式為
h(L1∪L2)=h(L1)∪h(L2),h(L1L2)=h(L1)h(L2),h(L∗)=h(L)∗.
對於連接,每個像 h(uv) 等於 h(u)h(v),並且每一對源字都給出這樣一個像。對於星號,源字是 L 中字的有限連接;其像是它們的像的有限連接。反之,像的每個有限連接都來自相應的源字的有限連接。零個因子的情形是 h(ε)=ε。這些等式給出對結構做歸納的證明,從而證明了替換構造。
例如,若 R=(a∣b)∗a,h(a)=xy,h(b)=ε,替換符號後得到 (xy∣ε)∗xy。其語言為 (xy)+。該構造可能產生冗餘的語法,但冗餘不影響所表示的語言。這也說明了,擦除可能產生 ε 因子,卻不會產生無限長的表達式。
逆像的詳細軌跡
設 K 為一元偶數長度語言,取 h(0)=a,h(1)=aa。其 DFA 有偶狀態 E 和奇狀態 O,每個 a 使兩者互換。在逆像 DFA 中,讀入 0 模擬一次互換,故 E↔O。讀入 1 模擬兩次互換,回到同一狀態。
對於源字 1010,逆像機器依次經過 E1E0O1O0E 並接受。其像是 aa,接著 a,再 aa,再 a,是長度為 6 的字。對於源字 101,機器停在 O,其像長度為 5,是奇數。分塊模擬的不變式在每個前綴上都把這兩種描述聯繫起來,而不僅僅在終點。
一個源符號的像字可以包含多個輸出符號,因此長度為 t 的源輸入可以映為比 t 長得多或短得多的字。逆像 DFA 在構造轉移表時完成這些模擬。其之後的運行對每個源符號只用表中的一次轉移;預處理成本仍然取決於所指定的像的長度。
規模與表示成本
設用於正像的源 DFA 有 n 個狀態,且在 Σ 上是全的。它有 n∣Σ∣ 條轉移。對於像長為 ℓa 的符號 a,替換其所有轉移會增加 nmax{0,ℓa−1} 個中間狀態。因此該 ε-NFA 至多有
n+na∈Σ∑max{0,ℓa−1}
個狀態。若刪去不可達狀態,或轉移之間共享結構,個數可能更少;但這種簡單構造使用全新的中間狀態,以使反向運行的證明直接。替換邊的數目同樣以 na∑max{1,ℓa} 為界,其中被擦除的轉移算作一條 ε 邊。
對於 n 狀態 DFA 的逆像,每個對 (q,a) 對應的新轉移,是透過從 q 出發沿 h(a) 前進而算出的。直接實現需要 O(na∑(1+ℓa)) 的轉移表工作量,其中包括空像的情形。所得 DFA 仍有 n 個狀態,但寫出它的 n∣Σ∣ 個轉移表項也是成本的一部分。這些界假定字母表有限,且像字是顯式表示的。
擦除與運行
ε-NFA 可以有 ε 環。它們不會使正像語言的證明失效:接受要求一條有限運行,而每條有限的新運行都分解為有限多條替換路徑。被擦除的源轉移對應一個 ε 步,該步仍記錄了所用的是哪條源轉移。多個源字可以映為同一個輸出字,新自動機對它可能有多條接受運行。
例如,若源自動機接受 a∗ 且 h(a)=ε,則每個源字都映為空字串。像語言恰為 {ε},而不是由不同空字串構成的無限集合。替換後的自動機可以繞其 ε 環任意有限次,但所有這些運行消耗的是同一個字。語言的成員關係不計運行的條數。
反過來,一個目標字不一定有任何源原像。若 h(a)=xx 且源字母表為 {a},則每個像的長度都是偶數;x 不可能是任何源語言的正像中的元素。該構造透過完整的替換路徑來保證這一約束,而不是接受路徑的任意前綴。
為甚麼需要全新的中間狀態
設兩條源轉移的像有重疊的前綴。若它們的替換路徑不加小心地共用一個中間狀態,則新的運行可能進入某一條源轉移的路徑,卻沿著另一條源轉移的後繼離開。這樣連接出的路徑未必對應任何原轉移。給每條轉移配備各自的中間狀態,就避免了這種意外混合。
在一條完整路徑於某個原狀態結束之後,新運行可以再選一條替換路徑,正如舊自動機再選一條轉移那樣。若像長為一,則不需要中間狀態。若為零,則 ε 邊至少對應一條源轉移,即使來自不同轉移的相同 ε 邊只表示一次。這些情形使收縮論證對所有替換長度都是統一的。
逆像上的布爾運算
對任意目標語言 K1,K2⊆Γ∗,w 屬於 h−1(K1∩K2),恰指 h(w) 同時屬於兩個目標語言。因此
h−1(K1∩K2)=h−1(K1)∩h−1(K2).
同樣的逐點論證對並集以及相對於所指定字母表的補集也成立。它並不依賴正則性;正則性保證所得語言存在相應的有限自動機。
反例模式
正像不保持交集
一個誘人的說法是 h(L1∩L2)=h(L1)∩h(L2)。正像的表現則不同,因為兩個不同的源字可以映為同一個目標字。當 h(a)=h(b)=x 時,不相交的單元素語言 {a} 與 {b} 的像是重疊的。因此交集的像不一定等於像的交集。這種區別在於量詞與可能的碰撞,而與源語言是否正則無關。此處 L1={a},L2={b},所以 L1∩L2=∅,h(L1∩L2)=∅,而 h(L1)∩h(L2)={x}。一般只有包含關係 h(L1∩L2)⊆h(L1)∩h(L2) 成立。
總結
逆像透過在原 DFA 中模擬每個替換字來識別。正像則透過把源轉移替換為以輸出符號為標記的路徑來識別,被擦除的符號使用 ε 轉移。兩種構造都保持正則性。
練習
快速檢查
(若 h(a)=xy 且 h(b)=ε,求 h(abba)。)
解答 · 答案
h(abba)=xyεεxy=xyxy。
快速檢查
(當 h(a)=ε 時,使用的是甚麼逆像轉移?)
回想 δ∗(q,ε)。
解答 · 答案
它是每個狀態上的自環,因為 δ∗(q,ε)=q。
快速檢查
(為甚麼把正像的運行反推回源運行時,可能需要記住所走的是哪條替換路徑?)
解答 · 答案
不同的源符號可以有相同的像,所以僅憑所消耗的輸出字未必能確定是哪條源轉移。替換路徑上全新的中間狀態記錄了用的是哪條轉移,讓我們可以選擇一條對應的源轉移。
解答 · 答案
不。取 h(a)=h(b)=x,則不相交的源語言 {a} 與 {b} 的像都是 {x}。