有限树自动机 | Codeboy's Blog

形式陈述

有限状态自动机沿一个字逐步更新状态；有限树自动机把输入换成带符号的有根树，一个父节点的状态由它的符号及全部孩子的状态共同决定。本页只讨论有限、有序、无变量的树：左右孩子有别，每棵输入都是已经填满的具体树，而不是含待替换变量的表达式。

有限秩字母表 $\Sigma$ 为每个符号 $f$ 指定固定元数 $\operatorname{ar}(f)\in\mathbb N$ ，并至少含一个零元符号。树集合 $T_\Sigma$ 递归定义为：若 $f$ 的元数为 $k$ 且 $t_1,\ldots,t_k\in T_\Sigma$ ，则 $f(t_1,\ldots,t_k)\in T_\Sigma$ ； $k=0$ 时直接写 $f$ ，它是叶子。不同元数的同名符号必须先区分，不能让同一个符号临时决定孩子数。

一台非确定性自底向上有限树自动机为

\mathcal A=(Q,\Sigma,\Delta,F),

其中 $Q$ 是有限状态集， $F\subseteq Q$ 是接受集， $\Delta$ 是有限规则集。每条规则形如

f(q_1,\ldots,q_k)\to q, \qquad \operatorname{ar}(f)=k.

特别地，叶规则是 $a\to q$ ，它为零孩子节点提供状态，不需要另设一个沿树移动的初态。树 $t$ 上的运行是在每个节点赋予一个状态，使每个节点及其孩子满足一条规则；存在一个根状态属于 $F$ 的运行时， $t$ 被接受。没有合法运行的树自然被拒绝。这些树组成语言 $L(\mathcal A)\subseteq T_\Sigma$ 。

若每个符号和有序孩子状态元组至多对应一个父状态，机器是确定性的；若每个这样的元组恰好对应一个父状态，则还是完全的。以下子集构造产生完全确定性机器，并保持语言不变。

以 $Q$ 的幂集为状态集，定义

\begin{aligned} \delta_D(f,S_1,\ldots,S_k) &=\{q\in Q:\exists q_1\in S_1,\ldots,q_k\in S_k,\\ &\hspace{25mm} (f(q_1,\ldots,q_k)\to q)\in\Delta\},\\ F_D&=\{S\subseteq Q:S\cap F\ne\varnothing\}. \end{aligned}

零元符号的规则单独读作 $\delta_D(a)=\{q:a\to q\in\Delta\}$ 。因此每棵树都得到唯一的集合状态 $S(t)$ ；空集也是合法状态，表示原机器在该子树上没有运行。

子集构造为什么保留语言

对树结构作归纳，证明不变量

S(t)=\{q\in Q:\text{存在在 }t\text{ 上根状态为 }q\text{ 的运行}\}.

叶子时，两边都恰好枚举适用叶规则的右侧。设 $t=f(t_1,\ldots,t_k)$ ，并且结论对所有孩子成立。原运行若在根取 $q$ ，其孩子状态 $q_i$ 都属于 $S(t_i)$ ，且根处必须使用规则 $f(q_1,\ldots,q_k)\to q$ ，所以 $q$ 被子集转移收集。反之，子集转移收集到的每个 $q$ 都有这样一组 $q_i$ ；归纳假设为每个孩子提供一条根状态为 $q_i$ 的运行。不同子树的节点互不相交，因此这些运行可以同时接到该根规则之下，得到整树运行。

归纳完成后， $S(t)\cap F\ne\varnothing$ 恰好表示至少一条原运行接受。候选集合至多有 $2^{|Q|}$ 个，实际构造可从叶集合开始，反复加入已有集合元组经各符号转移得到的新集合，直到闭合；每个加入的集合都有一棵输入树作到达见证。

直觉

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

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

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

同一棵树自底向上得到两个可达集合状态，确定性自顶向下则被交叉组合迫使误收全 b 树 — 上部箭头由叶指向根，表示子树状态的汇总；下部两个合法输入迫使左右状态都许可 b，因而误收 f(b,b)。

例子与边界

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

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

\begin{array}{lll} a\to U,&a\to A,&b\to U,\\ f(U,U)\to U,&f(A,U)\to A,&f(U,A)\to A. \end{array}

$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$ ；规则不必穷举每种看似有意义的状态组合。

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

B=\{U\},\qquad C=\{U,A\}.

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

左孩子	右孩子	父状态	是否接受
$B$	$B$	$B$	否
$B$	$C$	$C$	是
$C$	$B$	$C$	是
$C$	$C$	$C$	是

例如最后一行仍能使用 $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\xrightarrow{f}(q_1,\ldots,q_k),

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

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

q_0\xrightarrow{f}(q_L,q_R).

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

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

推论与应用

已给定树的识别成本

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

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

从局部规则到语法树检查

本例也可以写成树生成规则

A\to a\mid f(A,U)\mid f(U,A), \qquad U\to a\mid b\mid f(U,U),

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

语法树提供另一个应用入口：已给定一棵候选解析树时，有限状态可以检查每个节点的展开是否符合固定文法。若同一个非终结符在不同产生式中拥有不同孩子数，应先把标签编码为“符号、元数”，让输入落在固定秩字母表上。沿用语法树页把空产生式画成一个 $\varepsilon$ 叶子的约定时， $\varepsilon$ 是零元标签，而对应非终结符节点具有一个孩子。

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

参考资料

Hubert Comon 等，Tree Automata Techniques and Applications，1999 年 10 月 14 日版本。Preliminaries，第 11–12 页定义秩字母表与树；§1.1，第 14–20 页及 Theorem 4 给出自底向上运行与确定化；§1.6，第 31–32 页的 Theorem 8 与 Proposition 1 讨论自顶向下模型及确定性限制；§2.1.1–2.1.2，第 42–44 页讨论正则树文法；§2.4，第 53–55 页讨论与上下文无关文法的联系。本文六规则例子、两个可达子集与交叉组合反证是据这些定义展开的教学推导。

形式陈述 ​

子集构造为什么保留语言 ​

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

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

已给定树的识别成本 ​

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