摘要
引入了格值下推自动机、格值上下文无关文法及它们的语言的概念,证明了格值下推自动机以两种不同方式接受的语言类的等价性,研究了格值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.
出处
《计算机工程与应用》
CSCD
北大核心
2011年第25期34-38,48,共6页
Computer Engineering and Applications
基金
四川省科技厅重点科技项目(No.2006J13-035)
四川省教育厅重点实验室专项(No.2006ZD050)
关键词
格半群
格值下推自动机
格值上下文无关文法
格值语言
格值Chomsky范式文法
lattice-ordered monoid
lattice-valued pushdown automata
lattice-valued context-free grammar
lattice-valued language
Chomsky normal form grammar
