扩展可见下推自动机：多匹配与符号化探索

# 扩展可见下推自动机：多匹配与符号化探索 ## 1. 预备知识 ### 1.1 多匹配嵌套关系 在一个线性序列中，位置可分为调用（call）、内部（internal）和返回（return）。为实现 n 对 1 和 1 对 n 的匹配，引入了内部调用（inner - call）和内部返回（inner - return）。 - **n 对 1 匹配**：由一个调用、多个内部调用和一个返回实现。 - **1 对 n 匹配**：由一个调用、多个内部返回和一个返回实现。 假设用从 -∞ 开始的边表示待处理的调用边，用指向 +∞ 的边表示待处理的返回边。 **定义 1（多匹配嵌套关系）**：长度为 m（m ≥ 0）的多匹配嵌套关系 ⇝ 是 { -∞, 1, 2, · · ·, m} × {1, 2, · · ·, m, +∞} 的一个子集，对于任意的 i ⇝ j 和 i′ ⇝ j′，满足： 1. 嵌套边只能向前（i < j）。 2. 嵌套边不交叉（i < i′ ≤ j < j′ 不成立）。 3. 嵌套边只有一端可以与其他边共享。 若 i ⇝ j，i 称为调用，j 称为返回。特别地，当 j = +∞ 时，i 是待处理调用；当 i = -∞ 时，j 是待处理返回。若有 n 条不同的嵌套边共享同一个调用 i（即 i ⇝ jk，1 ≤ k ≤ n，1 ≤ i < j1 < j2 < · · · < jn ≤ m），i ⇝ jn 是最外层嵌套边，对于每个内层嵌套边，jh（1 ≤ h < n）被标识为内部返回。同理，若有 n 条不同的嵌套边共享同一个返回 j（即 ik ⇝ j，1 ≤ i1 < i2 < · · · < in < j ≤ m），每个 ih（1 < h ≤ n）被标识为内部返回。若一个位置既不是调用（或内部调用）也不是返回（或内部返回），则它是内部位置。如果没有待处理调用或待处理返回，多匹配嵌套关系是匹配良好的。 ### 1.2 单词编码 给定一个多匹配嵌套关系，通过为每个位置分配一个符号可以得到一个单词。为区分不同的位置类别，引入了带标签的字母表 $\hat{\Sigma} = \Sigma_c \cup \dot{\Sigma}_c \cup \Sigma_i \cup \dot{\Sigma}_r \cup \Sigma_r$，其中： - $\Sigma_c = \{<a_1|a_1 \in \Sigma\}$：调用符号。 - $\dot{\Sigma}_c = \{< \dot{a}_2|a_2 \in \Sigma\}$：内部调用符号。 - $\Sigma_i = \Sigma$：内部符号。 - $\dot{\Sigma}_r = \{ \dot{a}_3>|a_3 \in \Sigma\}$：内部返回符号。 - $\Sigma_r = \{a_4>|a_4 \in \Sigma\}$：返回符号。 $\Sigma$ 是普通字母表。注意，$<a_1$、$< \dot{a}_2$、$\dot{a}_3>$ 和 $a_4>$ 当且仅当 $a_1 = a_2 = a_3 = a_4$ 时才表示匹配。 所有基于 $\hat{\Sigma}$ 的多匹配嵌套单词的集合记为 $MNW(\hat{\Sigma})$，由于符号匹配的要求，$MNW(\hat{\Sigma}) \subset \hat{\Sigma}^*$。 ## 2. 多匹配可见下推自动机 ### 2.1 模型 **定义 2（多匹配可见下推自动机，MVPA）**：多匹配可见下推自动机是一个元组 $M = (Q, Q_0, F, \hat{\Sigma}, \Gamma, \delta)$，其中： - $Q$、$Q_0 \subseteq Q$、$F \subseteq Q$ 分别是有限状态集、初始状态集和最终状态集。 - $\hat{\Sigma} = \Sigma_c \cup \dot{\Sigma}_c \cup \Sigma_i \cup \dot{\Sigma}_r \cup \Sigma_r$ 是有限输入符号集，$\Sigma_c$、$\dot{\Sigma}_c$、$\Sigma_i$、$\dot{\Sigma}_r$ 和 $\Sigma_r$ 分别表示调用、内部调用、内部、内部返回和返回符号。 - $\Gamma \subseteq (\Sigma_c \cup \dot{\Sigma}_c \cup \dot{\Sigma}_r) \times \Xi \cup \{K\}$ 是有限栈元素集，包含一个特殊的栈底符号 $K$，$\Xi$ 是有限字母表。 - $\delta$ 是有限转移集，由以下四部分组成： - $\delta_c \subseteq Q \times \Sigma_c \times Q \times (\Sigma_c \times \Xi)$ - $\delta_i \subseteq Q \times \Sigma_i \times Q$ - $\delta_u \subseteq Q \times \Gamma \times (\dot{\Sigma}_c \cup \dot{\Sigma}_r) \times Q \times \Gamma$ - $\delta_r \subseteq Q \times \Gamma \times \Sigma_r \times Q$ **转移分类**： 1. **调用转移（压栈转移）**：$(q, <a, q', <a\xi) \in \delta_c$，当在状态 $q$ 读取调用 $<a$ 时，自动机转移到状态 $q'$，同时将调用 $<a$ 和符号 $\xi \in \Xi$ 压入栈。 2. **内部转移**：$(q, i, q') \in \delta_i$，对于内部符号 $i$，操作类似于普通有限自动机，仅更新状态从 $q$ 到 $q'$，栈不变。 3. **更新转移**： - **内部调用更新**：当 $x = <\dot{a}$ 是内部调用时，栈顶符号必须是 $<a$ 或 $<\dot{a}$，状态更新到 $q'$，栈顶从 $\gamma = <a\xi/<\dot{a}\xi$ 变为 $\gamma' = <\dot{a}\xi'$（$\xi, \xi' \in \Xi$）。 - **内部返回更新**：当 $x = \dot{a}>$ 是内部返回时，类似内部调用情况，栈顶从 $\gamma_1 = <a\xi/\dot{a}>\xi$ 变为 $\gamma_2 = \dot{a}>\xi'$。 4. **返回转移（弹栈转移）**： - 当输入返回符号 $a>$ 时，栈顶 $\gamma = x\xi$，$x$ 只能是 $<a$、$<\dot{a}$ 或 $\dot{a}>$，自动机转移到 $q'$ 并弹出栈顶。 - 当栈为空（$\gamma = K$）时，仅更新状态，栈不变。 栈 $\sigma$ 是 $\Gamma$ 上的有限单词，所有栈构成集合 $St = (\Gamma \setminus \{K\})^* \cdot \{K\}$。自动机的一个配置是一个对 $(q, \sigma)$，其中 $q \in Q$，$\sigma \in St$。一个单词 $w = w_1w_2 · · · w_n$ 若存在自动机 $M$ 在 $w$ 上的运行，则被 $M$ 接受。运行 $\rho$ 是一个非空的配置序列 $\rho = (q_0, \sigma_0) \xrightarrow{w_1} (q_1, \sigma_1) \xrightarrow{w_2} · · · \xrightarrow{w_n} (q_n, \sigma_n)$，其中 $q_0 \in Q_0$ 是初始状态，$\sigma_0 = K$。若 $q_n \in F$ 且 $\sigma_n \in (\Sigma_c \times \Xi)^* \cdot \{K\}$，则运行 $\rho$ 被 $M$ 接受。被 $M$ 接受的多匹配嵌套单词的集合构成语言 $L(M)$。 ### 2.2 确