适配非确定自顶向下树自动机定义以匹配Doner风格的技术问询

嘿，我来帮你梳理怎么把非确定自顶向下树自动机的定义调整得和Doner的自底向上风格一致。先回顾下两边的原始定义：

Doner (1970) 的自底向上树自动机定义 #

A bottom-up tree automaton is a tuple $\mathcal{A} = \langle Q, \Sigma, \delta, q_0, F \rangle$ where

• $Q$ is a finite set of states.
• $\Sigma$ is an alphabet.
• $\delta: Q \times Q \times \Sigma \to Q$ is the transition function.
• $q_0 \in Q$ is the initial state.
• $F \subseteq Q$ is the set of final states.

Associated with $\mathcal{A}$ is the function $\delta': \Sigma^{#} \to Q$ defined by $\delta'(\Lambda) = q_0$, $\delta'(\sigma[\tau, \tau']) = \delta(\delta'(\tau), \delta'(\tau'), \sigma)$ for all $\sigma \in \Sigma$ and $\tau, \tau' \in \Sigma^{#}$. $\mathcal{A}$ accepts a tree $\tau \in \Sigma^{#}$ if $\delta'(\tau) \in F$. $T(\mathcal{A})$ is the set of $\Sigma$-trees accepted by $\mathcal{A}$.

你的非确定自顶向下树自动机原始定义 #

A non-deterministic top-down tree automaton is a tuple $\mathcal{A} = \left(Q, \Sigma, \delta, q_0, F\right)$, where

• $Q$ is a finite set of states.
• $\Sigma$ is an alphabet.
• $\delta: Q \times \Sigma \rightarrow \mathcal{P}(Q \times Q)$ is the transition function.
• $q_0$ is the initial state.
• $F \subseteq Q$ is the set of final states.

A run $\varrho$ of $\mathcal{A}$ on $t \in T_{\Sigma}$ is a $Q$-labelled tree $\varrho$ with $\operatorname{dom}(\varrho)= {\lambda} \cup {u b \mid u \in \operatorname{dom}(t), b \in{0,1}}$ such that $\varrho(\lambda)=q_0$, and $(\varrho(u 0), \varrho(u 1)) \in \delta(\varrho(u), t(u))$, for all $u \in \operatorname{dom}(t)$.

$\varrho$ is accepting if all leaves of $\varrho$ are labeled with states in $F$, i.e. $\varrho(u) \in F$, for all $u \in \operatorname{dom}(\varrho) \backslash \operatorname{dom}(t)$.

A tree $t$ is recognized by $\mathcal{A}$ if there is an accepting run of $\mathcal{A}$ on $t$. $T(\mathcal{A})$ denotes the set of trees that are recognized by $\mathcal{A}$.

适配方案：贴合Doner的简洁风格 #

Doner的定义核心是用一个递归函数直接绑定自动机的行为和接受条件，去掉了中间的“运行（run）”概念。我们可以把自顶向下自动机的非确定性接受逻辑也包装成类似的递归谓词/函数，让结构完全对齐：

调整后的非确定自顶向下树自动机定义 #

A non-deterministic top-down tree automaton is a tuple $\mathcal{A} = \langle Q, \Sigma, \delta, q_0, F \rangle$ where

• $Q$ is a finite set of states.
• $\Sigma$ is an alphabet.
• $\delta: Q \times \Sigma \to \mathcal{P}(Q \times Q)$ is the transition function.
• $q_0 \in Q$ is the initial state.
• $F \subseteq Q$ is the set of final states.

Associated with $\mathcal{A}$ is the boolean-valued function $\delta': Q \times T_{\Sigma} \to {\text{true}, \text{false}}$ defined recursively:

• For the empty leaf tree $\Lambda$, $\delta'(q, \Lambda) = \text{true}$ if and only if $q \in F$.
• For a composite tree $\sigma[t_0, t_1] \in T_{\Sigma}$, $\delta'(q, \sigma[t_0, t_1]) = \text{true}$ if and only if there exists some pair $(q_0, q_1) \in \delta(q, \sigma)$ such that $\delta'(q_0, t_0) = \text{true}$ and $\delta'(q_1, t_1) = \text{true}$.

$\mathcal{A}$ accepts a tree $t \in T_{\Sigma}$ if $\delta'(q_0, t) = \text{true}$. $T(\mathcal{A})$ is the set of all $\Sigma$-trees accepted by $\mathcal{A}$, i.e. $T(\mathcal{A}) = { t \in T_{\Sigma} \mid \delta'(q_0, t) = \text{true} }$.

适配思路说明 #

1. 对齐结构：保留五元组定义 + 递归函数绑定行为 + 接受集合定义的三段式结构，和Doner的定义一一对应。
2. 简化概念：把“接受运行”的逻辑直接嵌入到递归函数$\delta'$中——非确定性的状态选择（存在$(q_0,q_1)$）和叶子状态的最终性要求（$q \in F$）都通过函数的递归规则体现，不需要单独定义“run”和“accepting run”。
3. 保持严谨性：递归函数的规则完全等价于原始定义中的接受条件：从初始状态出发，能找到一条状态转移路径，让所有叶子节点的状态都落在最终状态集合$F$中。

备注：内容来源于stack exchange，提问作者user1868607