格值下推自动机与格值上下文无关文法

摘要：

引入了格值下推自动机、格值上下文无关文法及它们的语言的概念,证明了格值下推自动机以两种不同方式接受的语言类的等价性,研究了格值Chomsky范式文法、格值上下文无关文法及其派生所产生的语言的等价条件,揭示了在一定条件下,格值下推自动机接受的语言类与格值上下文无关文法产生的语言类的等价性,证明了有理格值语言均被格值下推自动机识别.

关键词：格半群、格值下推自动机、格值上下文无关文法、格值语言、格值Chomsky范式文法

所属期刊栏目：47

分类号：TP301.1(计算技术、计算机技术)

资助基金：四川省科技厅重点科技项目2006J13-035;四川省教育厅重点实验室专项2006ZD050

在线出版日期：2012-01-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：34-38,48