嵌入下推自动机

维基百科,自由的百科全书
跳转至: 导航搜索

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

历史和应用[编辑]

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

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

理论[编辑]

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

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

我们定义 EPDA 为七元组

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

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

一个给定的格局被定义为

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

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

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

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

引用[编辑]

  1. ^ Vijay-Shanker, K. A Study of Tree-Adjoining Grammars. Ph.D. Thesis (University of Pennsylvania). 1988.January. 
  2. ^ Weir, David J. Linear Iterated Pushdowns. Computational Intelligence. 1994, 10: 431––439 [2007-11-21]. 
  3. ^ Joshi, Aravind K.; Yves Schabes. Tree-Adjoining Grammars. Handbook of Formal Languages (Springer). 1997, 3: 69––124 [2007-11-21].