动机
改变字母表可能揭示或隐藏语言的结构。同态把每个输入符号替换为一个固定的字(可以是空串),并通过连接把这种替换扩展到整个字。正则语言在正像与逆像下都保持正则,但这两种构造的方向不同。
对于逆像,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}。