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

Lattice-valued pushdown automata and lattice-valued context-free grammars

作　　者：彭家寅[1,2] 

机构地区：[1]四川省高等学校数值仿真重点实验室,四川内江641100 [2]内江师范学院数学与信息科学学院,四川内江641100

出　　处：《计算机工程与应用》2011年第25期34-38,48,共6页Computer Engineering and Applications

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

摘　　要：引入了格值下推自动机、格值上下文无关文法及它们的语言的概念,证明了格值下推自动机以两种不同方式接受的语言类的等价性,研究了格值Chomsky范式文法、格值上下文无关文法及其派生所产生的语言的等价条件,揭示了在一定条件下,格值下推自动机接受的语言类与格值上下文无关文法产生的语言类的等价性,证明了有理格值语言均被格值下推自动机识别。The concepts of lattice-valued pushdown automata,lattice-valued context-free grammars and their languages are proposed.The equivalent relation which a lattice-valued language can be accepted by lattice-valued pushdown automata in two different ways is proved.The equivalent conditions of three kinds of lattice-valued languages generated by lattice-valued Chomsky normal form grammar and lattice-valued context-free grammars and derivations of lattice-valued context-free grammars are investigated.It is revealed that under certain conditions the language accepted by lattice-valued pushdown automata is equivalent to that generated by a lattice-valued context-free grammar.It is indicated that each rational lattice-valued language is recognized by a lattice-valued pushdown automaton.

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

分 类 号：TP301.1[自动化与计算机技术—计算机系统结构]