(2) 阅读 (1098)

全局索引语法 编辑

词条创建者 匿名用户

全局索引语法

编辑

全局索引语法(GIGs)是Castaño(2004)介绍的一类语法,目的是对一些现象进行建模,包括自然语言语法和基因组语法。对GIGs最简单的描述是通过与索引语法的比较。在索引式语法中,每个非终端符号都有一个索引堆栈,并且可以根据推导过程的不同而变化,而在GIG中,有一个单一的全局索引堆栈,在推导过程中被操作(对于任何将符号推到堆栈中的重写操作,它都是严格的最左边)。由于全局堆栈的存在,当没有非终端符号需要重写,并且堆栈为空时,GIG推导被认为是完整的。规则描述GIG规则基本上有四种形式:无条件做某事的规则,以堆栈最上面的符号为条件做某事的规则,向堆栈推送的规则,以及从堆栈弹出的规则。我们可以将这些规则依次记为其中f是任何索引符号,α是任何终端和/或非终端符号的字符串,x是一个终端是一个终端符号。因为偶尔重写规则可能需要以堆栈在某种意义上是空的为条件,所以符号#被用作最底层的堆栈符号,这意味着一个空的堆栈正好包含一个符号,#。

全局索引语法

第三种规则形式,即推送规则,应该指出,因为它与弹出规则不同,要求所有的推送操作至少要给派生字符串引入一个新的终端符号。如果没有这个约束,这类语法将是Type-0,因此是图灵完全的。

全局索引语法的例子

编辑

在这个例子中,我们将通过把推导字符串放在一个堆栈上来表示推导的步骤,如{displaystyle{p(a{n}b{n}c{n}):ngeq1}},其中p是字符串互换函数,它被猜测(但未被证明)为不可表示为索引语言。,其中p是字符串互换函数,据猜测(但没有证明),它不能作为一种索引语言来表示。目前还不知道是否所有的IG也是GIG。GIGs和IGs完全有可能描述CSLs的仅仅重叠的子集。trGIGsGIGs的一个子类是trGIGs,它通过要求pop规则在派生中至少引入一个终端符号,使pop和push规则统一。

全局索引语法的例子

编辑

这种语法的一个例子,描述了语言的特点{displaystyle{a{m}b{n}c{m}d{n}:m,ngeq1}}。{displaystyle{begin{array}{l}StoAD\AtoaAc~|~aBc\B{xrightarrow[{+f}]{}}bB~|~b\D{xrightarrow[{-f}]{}}dD~|~dend{array}}}那么字符串aabbbccddd的推导就是。{displaystyle{begin{aligned}{frac{S}{[[#]}}&to{frac{AD}{[[#]}}.


内容由匿名用户提供,本内容不代表vibaike.com立场,内容投诉举报请联系vibaike.com客服。如若转载,请注明出处:https://vibaike.com/163899/

发表评论

登录后才能评论

词条目录
  1. 全局索引语法
  2. 全局索引语法的例子
  3. 全局索引语法的例子

轻触这里

关闭目录

目录