有限树自动机

树状态概括的是“一整棵子树对上层还有什么影响”。一个父节点无需知道孩子内部的每次选择，只需知道各孩子可能交上来的状态，再决定哪些组合符合规则。字自动机只合并一条前缀上的候选，树自动机则要在同一个父节点合并多个有序孩子的候选。

非确定性并不要求每条运行都成功。对某棵子树，同时存在普通状态与接受意义更强的状态完全合理；父节点可以选择其中一个。确定化保留全部可能性，既不能随意丢掉候选，也不能把“存在一个接受状态”改成“集合中所有状态都接受”。

方向在这里影响信息何时可用。自底向上时，父节点已经收到了各子树的摘要；自顶向下时，根必须先给孩子分派任务，然后孩子才继续处理自己的输入。这解释了为什么自底向上可以确定化，而自顶向下的确定性限制会丢失表达能力。

从六条规则算出两个集合状态 ​

固定 $\mathrm{\Sigma }=\{a:0,b:0,f:2\}$，目标语言 $L$ 是“至少有一个 $a$ 叶子”的全部树。取 $Q=\{U,A\}$、$F=\{A\}$，规则恰好为

$U$ 表示任意子树，$A$ 表示含有 $a$ 的子树。归纳可知每棵树都有根状态为 $U$ 的运行：叶子使用相应 $U$ 规则，内部使用 $f(U,U)\to U$。另一项归纳给出：有 $A$ 运行当且仅当树含 $a$。叶子只有 $a$ 可取 $A$；内部若某孩子含 $a$，就让该孩子取 $A$，另一个孩子取始终可用的 $U$，由相应规则得到 $A$。反方向则由产生 $A$ 的规则追到某个 $a$ 叶子。

这也说明为何无需添加 $f(A,A)\to A$。即使两个孩子都含 $a$，也可以只选一边的 $A$ 运行，另一边选 $U$；规则不必穷举每种看似有意义的状态组合。

从叶子开始，只有下面两个集合可达：

$a$ 到 $C$，$b$ 到 $B$，二元转移为：

例如最后一行仍能使用 $f(A,U)\to A$，因为 $A,U\in C$。四个组合都留在 $\{B,C\}$ 内，而两者又各有叶子见证，所以它们恰好是全部可达子集；$\varnothing$ 与 $\{A\}$ 在本例中不可达。

对 $t=f(f(a,b),b)$，先给三个叶子赋 $C,B,B$，内层 $f$ 得 ${\delta }_D(f,C,B)=C$，根得 ${\delta }_D(f,C,B)=C$，因此接受。把唯一的 $a$ 改成 $b$ 后，叶子、内层和根全为 $B$，因此拒绝。这一计算同时展示了节点处理次序：先孩子、后父亲，而不是沿某条根到叶路径读完便下结论。

同一语言为何不能确定性自顶向下识别 ​

这里的自顶向下模型有单个初态 $q_0$，规则写成

每个状态—符号对至多一条规则。根从 $q_0$ 开始，规则将状态分派给各孩子；零元规则 $q\stackrel{a}{\to }()$ 允许该叶结束。所有节点都能使用规则才接受。这个定义没有前瞻，没有兄弟节点通信，也没有多个初态供选择。

假设一台这样的机器识别 $L$。由于 $f(a,b)$ 和 $f(b,a)$ 都属于 $L$，根遇到 $f$ 时必须使用同一条规则

第一个输入的接受要求 $q_L$ 允许 $a$、$q_R$ 允许 $b$；第二个要求 $q_L$ 允许 $b$、$q_R$ 允许 $a$。于是 $f(b,b)$ 在根使用相同规则、左右叶分别使用这两条 $b$ 规则，也被接受。但它没有 $a$，矛盾。因此这个可由两态自底向上机器识别的语言不属于确定性自顶向下语言类。

非确定性自顶向下则能识别它：把上述六条底向上规则反向解释，根初态取 $A$，遇到 $f$ 时猜把“必须找到 $a$”的任务交给左侧还是右侧，另一侧取 $U$。成功运行正好对应原机器根为 $A$ 的运行。一般机器可以允许初态从 $F$ 中非确定选择；反转规则保留运行，却不保留确定性。上面的不可识别证明依赖明确的单初态确定性约定，不能照搬到带前瞻的扩展模型。

有环却没有任何接受树 ​

识别给定的树，与判断“是否存在某棵接受树”不同。仍用 $\{a:0,b:0,f:2\}$，另取状态集 $\{p,q,r,d,e\}$、接受集 $\{d\}$，规则恰好为

从叶规则出发，一轮只使用上一轮已经具备的孩子状态，可达集合依次是

$q$ 的循环能从 $p$ 启动；$d,e$ 虽相互依赖，却没有任何叶子为它们提供起点。于是接受态 $d$ 不可达，语言为空。不能把 $f(d,p)\to e$ 画成普通图边后，因 $p$ 可达便宣布 $e$ 可达：规则要求两个孩子同时有见证。

若只把接受集改为 $\{r\}$，就有接受树 $f(f(a,a),f(a,a))$，共七个节点。它可以共享两个相同的孩子子树作紧凑存储，但作为输入树，两个出现位置仍各算三个节点。

对同一字母表作语言差 ​

回到原来的语言 $L$：“至少有一个 $a$ 叶子”。再定义 $K$：“最左叶子是 $a$”。令 $V$ 表示任意子树，$L_a$ 表示满足后者的子树，用五条规则

以及接受集 $\{L_a\}$ 识别 $K$。沿左孩子下降的归纳说明 $L_a$ 恰好具有该含义；右孩子始终可用 $V$ 运行。

这个机器确定化后只有两个可达集合

对二元符号，父状态只看左孩子：左为 $E$ 时得到 $E$，左为 $H$ 时得到 $H$，无论右侧是哪个集合。这已经覆盖两态的全部四种孩子组合，所以限制到 $\{E,H\}$ 后仍是完全确定性机器，接受态为 $H$。

将它与前面的 $B,C$ 机器同步执行。命名四个乘积状态：

叶子 $a$ 到 $X$，$b$ 到 $Y$。从叶子开始实际只有 $X,Y,Z$ 可达，其完整转移表为：

三态对所有组合闭合，$Z$ 由 $f(b,a)$ 到达，所以它们恰为可达态。$W$ 要求“没有 $a$，但最左叶是 $a$”，不可能由具体树到达。

因此 $L\setminus K$ 只接受 $Z$，最小见证是三个节点的 $f(b,a)$；两个单节点树 $a,b$ 都不能见证这个差。反向差 $K\setminus L$ 只接受不可达的 $W$，所以为空。这个乘积既给出 $K\subseteq L$ 的证据，也给出 $L⊈K$ 的反例。

为什么不能直接交换任意机器的接受态 ​

原六规则 NFTA 的每棵树都有 $U$ 运行。若直接把接受集 $\{A\}$ 换成 $\{U\}$，新机器会接受所有树，连原本已接受的 $a$ 也仍被接受，当然不是补集。拒绝某一条运行不等于不存在其他接受运行。

即使机器确定，缺规则也会导致错误。单态 $p$、接受集 $\{p\}$、唯一规则 $a\to p$ 只接受 $a$；交换成空接受集后，$b$ 依然没有运行，而它本应属于补集。应先加非接受汇点 $\mathrm{\perp }$：$b$ 到 $\mathrm{\perp }$，四种二元孩子状态组合也全到 $\mathrm{\perp }$，再交换接受集。只有完全确定性保证每棵树恰有一条运行，才能用接受与拒绝互换表示语言补集。

空性闭包与线性工作队列 ​

对一般 NFTA，从 $R_0=\varnothing$ 开始同步更新

零元规则没有孩子前提，首轮就加入其右侧。约定叶高为一，则 $R_i$ 恰是某棵高度至多 $i$ 的树可以到达的根状态集合：叶子给出基例；若孩子已有见证，把它们接在适用根规则下就得到新见证；反向把一棵树拆成根和孩子，同样落在这个更新式中。

每轮若变化就至少增加一个状态；一旦某轮不变，以后也不再变化。故至多 $|Q|$ 轮添加后得到闭包 $R$，并且

逐轮扫描显式规则表需 $O(|Q|\Vert \mathcal{A}\Vert )$ 时间。空性本身可更快：为每条规则保存尚未满足的孩子位置数，为每个状态保存它在各规则中的出现位置。状态首次到达时进入队列，把这些位置的计数各减一；某规则计数归零，才将其右侧激活。零元规则直接启动。

状态只激活一次，每个孩子位置只处理一次，因此总时间为 $O(\Vert \mathcal{A}\Vert )$。重复位置不能合并：$f(q,q)\to r$ 有两个待满足位置，$q$ 激活时应各减一次。首次激活时保存一条适用规则，可以恢复一棵见证；这个存在性过程尚未保证它的节点数最小。

最小节点见证的动态规划 ​

这个最小节点递推是一项动态规划公理库动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。：状态取“高度上界、根状态”，每层只依赖前一层，因而即使原规则的状态依赖有环，展开后的有限填表顺序仍然良基。

令 $m_0(q)=\mathrm{\infty }$，同步计算

叶规则的空和为零，因此成本为一；没有候选取 $\mathrm{\infty }$。右侧必须全部使用上一轮数值。归纳不变量是：$m_i(q)$ 等于所有高度至多 $i$、根状态为 $q$ 的运行所对应树的最小节点数。根贡献一个节点，孩子贡献相加，反向将各个最优孩子接在一起即可达到候选值。即使两孩子选了同一状态，也必须加两次成本。

为什么只需 $|Q|$ 轮？为某个可达状态选一棵节点数最少的树及其运行。如果一条根叶路径上有两个节点状态相同，就能把祖先节点的整个子树替换为该后代的子树。上层仍看到同一状态，运行合法，节点数却严格减少，矛盾。因此最小树的任何根叶路径都不重复状态，高度至多 $|Q|$，于是 $m_{|Q|}$ 已给出全局最优值。

在前面的含环例中，完整成本更新为：

第四轮与第三轮完全相同，可以提前停止。接受 $d$ 时最优成本为无穷；改接受 $r$ 时成本为七。语言差例则给出 $m(X)=m(Y)=1$、$m(Z)=3$、$m(W)=\mathrm{\infty }$。

首次发现的树可能不是最小节点树。例如规则 $a\to p$、$f(p,p)\to r$、$f(r,r)\to s$、$f(r,p)\to s$ 中，若先保存 $f(r,r)$ 作为 $s$ 的见证，得到七个节点；后一个选择只需五个节点。两树高度都为三，所以最早的高度轮次也不足以解决节点数最优。

动态规划需 $O(|Q|\Vert \mathcal{A}\Vert )$ 次整数算术操作，这与线性空性算法的成本不同。数值可以很大：最大元数为 $d$ 时，一棵高度至多 $|Q|$ 的树最多有 $1+d+\cdots +d^{|Q|-1}$ 个节点，二元情形为 $2^{|Q|}-1$；算术操作数不能自动当作固定位宽成本。

对每个有限成本状态选一条达到最小值的规则，其每个孩子成本都严格小于父成本，所以这些选择构成无环图。每状态一个共享节点、保留有序且可重复的孩子边，便得到至多 $|Q|$ 个顶点的见证 DAG；把共享出现逐次展开后才是输入树，输出所需时间至少与展开大小相称。

差语言与等价检查 ​

给定同一秩字母表上的 $\mathcal{A},\mathcal{K}$，要构造 $L(\mathcal{A})\setminus L(\mathcal{K})$，先将右侧完全确定化，再交换其接受态，最后与左侧作同步乘积。左侧可以仍是非确定性的；乘积在每个节点同时使用同一输入符号的两条规则，接受条件为“左接受、右不接受”。

右侧每棵树恰有一个运行，因而乘积有接受运行，当且仅当左侧有接受运行而右侧拒绝。对乘积再用空性闭包，就能判断包含关系；交换左右做第二次差，两者都为空恰好等价。非空时，上述成本递推给出最小节点反例树。

这些成本按实际构造后的显式机器计。右侧确定化可能产生指数多状态，不能把最终乘积上的线性空性成本宣称为原始两个 NFTA 输入上的线性包含判定。只保留可达子集是合法节省，但它们必须已对所有符号与孩子组合闭合。

已给定树的识别成本 ​

若完全确定性机器及其转移表固定，对含 $n$ 个节点的树作一次后序遍历，每个节点查一次表，时间是 $O(n)$。遍历仍需要管理树的结构；递归执行时控制栈可达 $O(h)$，其中 $h$ 是树高，不能从字 DFA 的有限控制状态推出整项执行只用常数内存。

非确定性机器也可以直接在节点计算 $S(t)$，无需先构造指数大的完整表。若以位集表示状态集合，并在每个节点扫描匹配符号的显式规则，成员测试按常数成本计，时间可界为 $O(n\Vert \mathcal{A}\Vert )$；这里规则表示长度计入所有孩子状态位置以及状态集。为每个节点保留结果的直接实现使用 $O(n|Q|)$ 位。提前确定化和运行时维护集合共享同一不变量，但付费时点不同。

从局部规则到语法树检查 ​

最初的“含有 $a$ 叶子”语言 $L$ 也可以写成树生成规则

以 $A$ 为开始符号，生成的具体树正好是 $L$。生成过程从根向下选规则，识别过程在给定树上验证是否存在相容规则；前面的归纳已经证明这两个描述在本例中相同。

语法树公理库语法树Parse tree · Derivation tree用有序树记录产生式层次，以完整例子区分推导顺序、文法歧义、优先级及抽象语法树。提供另一个应用入口：已给定一棵候选解析树时，有限状态可以检查每个节点的展开是否符合固定文法。若同一个非终结符在不同产生式中拥有不同孩子数，应先把标签编码为“符号、元数”，让输入落在固定秩字母表上。沿用语法树页把空产生式画成一个 $\epsilon$ 叶子的约定时，$\epsilon$ 是零元标签，而对应非终结符节点具有一个孩子。

这里检查的是树结构。将合法树的叶子从左到右展开为字，会丢掉内部结构；可由有限树自动机识别的树，其产出语言不必是正则字语言。因此，能有限状态检查一棵已经提供的语法树，并不等于能用字 DFA 从字符串中完成同样的语法分析。

终点自测：重建五态含环例的可达集与成本表，解释有种子循环和无种子循环的区别；再从 $B,C$ 与 $E,H$ 两个表构造三个可达乘积态，证明 $f(b,a)$ 是最小差语言见证，并说明共享DAG为什么不能代替输入树的节点计数。

不要把它与交替奇偶字自动机公理库交替奇偶字自动机Alternating parity word automaton让正布尔转移组合存在选择与同时义务，以运行树的全部分支判断同一无限字，并解释对偶补集。的运行树混同。本页的输入就是一棵有限有序树，孩子可以携带不同的输入子树；交替字自动机的输入仍是一条无限字，同深度的全部运行副本读取同一个位置，树表达同时必须兑现的逻辑分支。