查看“︁嵌入下推自动机”︁的源代码

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

==历史和应用==

EPDA 最初由 K. Vijay-Shanker 在他 1998 年的博士论文中描述<ref>{{cite journal en|last=Vijay-Shanker |first=K. |authorlink= |coauthors= |title=A Study of Tree-Adjoining Grammars |journal=Ph.D. Thesis |publisher=[[University of Pennsylvania]] |volume= |issue= |pages= |id= |url= |accessdate= |quote= |date=January 1988}}</ref>。它们已经被应用于更完整的描述适度上下文有关文法类，并向[[乔姆斯基层级]]扩展和精细了这个文法类。各种子文法，比如[[线性附标文法]]可以从而定义<ref>{{cite journal en |last=Weir |first=David J. |authorlink= |coauthors= |year=1994 |month= |title=Linear Iterated Pushdowns |journal=Computational Intelligence |volume=10 |issue= |pages=431--439 |id= |url=http://www.informatics.sussex.ac.uk/users/davidw/papers/ci94.ps |accessdate=2007-11-21 |quote= |author= |archive-url=https://web.archive.org/web/20070216233834/http://www.informatics.sussex.ac.uk/users/davidw/papers/ci94.ps |archive-date=2007-02-16 |dead-url=yes }}</ref>。它们还在自然语言处理中扮演重要角色。

尽管自然语言有使用上下文无关文法来分析的传统(参见[[转换-生成语法]]和[[计算语言学]])，但这个模型不适合有交叉依赖的语言如荷兰语，而 EPDA 就适合。详细的语言分析可见于引文<ref>{{cite journal en |last=Joshi |first=Aravind K. |authorlink= |coauthors=Yves Schabes |year=1997 |month= |title=Tree-Adjoining Grammars |journal=Handbook of Formal Languages |publisher=Springer |volume=3 |issue= |pages=69--124 |id= |url=http://www.cis.upenn.edu/~cse477/ltag-paper.pdf |accessdate=2007-11-21 |quote= |deadurl=yes |archiveurl=https://web.archive.org/web/20070205023657/http://www.cis.upenn.edu/~cse477/ltag-paper.pdf |archivedate=2007-02-05 }}</ref>。

==理论==

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

每个栈都可以依据它的元素来定义，所以我们使用双剑符号来指示在自动机中的第 <math>\,j</math> 个栈: <math>\,\Upsilon_j = \ddagger\sigma_j = \{\sigma_{j,k}, \sigma_{j,k-1}, \ldots, \sigma_{j,1} \}</math>，这里的 <math>\,\sigma_k</math> 将是在栈中的下一个可访问的符号。<math>\,m</math> 个栈的“嵌入栈”因此可以指示为 <math>\,\{\Upsilon_j \} = \{\ddagger\sigma_m,\ddagger\sigma_{m-1}, \ldots, \ddagger\sigma_1 \} \in (\ddagger\Gamma^+)^*</math>。

我们定义 EPDA 为[[多元组|七元组]]

:<math>\,M = (Q, \Sigma, \Gamma, \delta, q_0, Q_\textrm{F}, \sigma_0)</math> 这里的

* <math>\,Q</math> 是“状态”的有限集合；
* <math>\,\Sigma</math> 是“输入字母表”的有限集合；
* <math>\,\Gamma</math> 是“栈字母表”的有限集合；
* <math>\,q_0 \in Q</math> 是“开始状态”；
* <math>\,Q_\textrm{F} \subseteq Q</math> 只“最终状态”的集合；
* <math>\,\sigma_0 \in \Gamma</math> 是“初始栈符号”
* <math>\,\delta : Q \times \Sigma \times \Gamma \rightarrow S</math> 是“转移函数”，这里的 <math>\,S</math> 是 <math>\,Q\times (\ddagger\Gamma^+)^* \times \Gamma^* \times (\ddagger\Gamma^+)^*</math> 的有限子集。

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

一个给定的格局被定义为

:<math>\,C(M) = \{q,\Upsilon_m \ldots \Upsilon_1, x_1, x_2\} \in Q\times (\ddagger\Gamma^+)^* \times \Sigma^* \times \Sigma^*</math>

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

:<math>\,L(M) = \left\{ x | \{q_0,\Upsilon_0,\epsilon,x\} \rightarrow_M^* \{q_\textrm{F},\Upsilon_m \ldots \Upsilon_1, x, \epsilon\} \right\}</math>

这里的 <math>\,q_\textrm{F} \in Q_\textrm{F}</math> 而 <math>\,\rightarrow_M^*</math> 定义转移函数按需要而多次应用来分析这个字符串。

==引用==
{{reflist}}

{{形式语言与形式文法}}

[[Category:自动机]]