嵌入下推自动机

嵌入下推自动机或 EPDA 是分析树-邻接文法(TAG)的计算模型。除了不再使用堆栈来存储符号之外，它类似于分析上下文无关文法的下推自动机。它有存储符号的重复堆栈组成的一个栈，这给予了 TAG 在上下文无关文法和上下文有关文法之间的复杂度，或者说是适度上下文有关文法的子集。

历史和应用

EPDA 最初由 K. Vijay-Shanker 在他 1998 年的博士论文中描述。它们已经被应用于更完整的描述适度上下文有关文法类，并向乔姆斯基层级扩展和精细了这个文法类。各种子文法，比如线性附标文法可以从而定义。它们还在自然语言处理中扮演重要角色。

尽管自然语言有使用上下文无关文法来分析的传统(参见转换-生成语法和计算语言学)，但这个模型不适合有交叉依赖的语言如荷兰语，而 EPDA 就适合。详细的语言分析可见于引文。

理论

首先重申 EPDA 是有一组其自身可以通过“嵌入栈”来访问的栈的有限状态机，每个栈包含“栈字母表” $\mathrm{\Gamma }$ 的元素，并且我们通过 ${\sigma }_i\in {\mathrm{\Gamma }}^{*}$ 定义一个栈的元素，这里的星号是字母表的Kleene闭包。

每个栈都可以依据它的元素来定义，所以我们使用双剑符号来指示在自动机中的第 $j$ 个栈: ${\mathrm{{\rm Y}}}_j=‡{\sigma }_j=\{{\sigma }_{j,k},{\sigma }_{j,k-1},\dots ,{\sigma }_{j,1}\}$，这里的 ${\sigma }_k$ 将是在栈中的下一个可访问的符号。$m$ 个栈的“嵌入栈”因此可以指示为 $\{{\mathrm{{\rm Y}}}_j\}=\{‡{\sigma }_m,‡{\sigma }_{m-1},\dots ,‡{\sigma }_1\}\in (‡{\mathrm{\Gamma }}^{+}{)}^{*}$。

我们定义 EPDA 为七元组

$M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,Q_{\text{F}},{\sigma }_0)$ 这里的

• $Q$ 是“状态”的有限集合；
• $\mathrm{\Sigma }$ 是“输入字母表”的有限集合；
• $\mathrm{\Gamma }$ 是“栈字母表”的有限集合；
• $q_0\in Q$ 是“开始状态”；
• $Q_{\text{F}}\subseteq Q$ 只“最终状态”的集合；
• ${\sigma }_0\in \mathrm{\Gamma }$ 是“初始栈符号”
• $\delta :Q\times \mathrm{\Sigma }\times \mathrm{\Gamma }\to S$ 是“转移函数”，这里的 $S$ 是 $Q\times (‡{\mathrm{\Gamma }}^{+}{)}^{*}\times {\mathrm{\Gamma }}^{*}\times (‡{\mathrm{\Gamma }}^{+}{)}^{*}$ 的有限子集。

所以转移函数选取一个状态，输入字符串的下一个符号，和当前栈的顶符号；并生成下一个状态，在“嵌入栈”上要压入和弹出的那些栈，当前栈的压入和弹出，和要在下一个转移中被当作当前栈的栈。更加概念的说，“嵌入栈”是被压入和弹出的，当前栈被随意的压回到“嵌入栈”，而你希望的任何其他栈将被压入它的顶部，带有最后的栈是在下一个重复中所读取的。所以，这些栈被同时压入当前栈的上面和下面。

一个给定的格局被定义为

$C(M)=\{q,{\mathrm{{\rm Y}}}_m\dots {\mathrm{{\rm Y}}}_1,x_1,x_2\}\in Q\times (‡{\mathrm{\Gamma }}^{+}{)}^{*}\times {\mathrm{\Sigma }}^{*}\times {\mathrm{\Sigma }}^{*}$

这里的 $q$ 是当前状态，$\mathrm{{\rm Y}}$ 是在“嵌入栈”中的栈，带有 ${\mathrm{{\rm Y}}}_m$ 是当前栈，而对于输入字符串 $x=x_1{x}_2\in {\mathrm{\Sigma }}^{*}$, $x_1$ 是已经被机器处理的那部分字符串，而 $x_2$ 是要处理的那部分，带有它的头部是当前所读的符号。注意空串 $ϵ\in \mathrm{\Sigma }$ 被隐含的定义为终止符号，如果机器处于最终状态此时读到空串，则整个输入字符串被“接受”，如果不是则“拒绝”。这种“接受”了的字符串是如下语言的元素

$L(M)=\{x|\{q_0,{\mathrm{{\rm Y}}}_0,ϵ,x\}\underset{M}{\overset{*}{\to }}\{q_{\text{F}},{\mathrm{{\rm Y}}}_m\dots {\mathrm{{\rm Y}}}_1,x,ϵ\}\}$

这里的 $q_{\text{F}}\in Q_{\text{F}}$ 而 $\underset{M}{\overset{*}{\to }}$ 定义转移函数按需要而多次应用来分析这个字符串。