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

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

格值上下文无关文法的范式

给出了格值上下文无关文法(LCFG),Chomsky范式文法,Greibach范式文法的定义.证明了对任意的LCFG存在与之等价的Chomsky范式文法;给出了对任意的LCFG,存在与之等价的Greibach范式文法的条件.文中结论表明了LCFG的特性与其取值格的代数性质密切相关.

格值上下文无关文法的代数刻画

在格值逻辑框架下给出上下文无关文法及上下文无关语言的概念,给出格值逻辑意义下广义的格值子集构造方法,并证明了任一与除一步推导为格值以外,其余推导都是经典推导的之间的相互等价性。

上下文无关格值词语言研究

文章在格半群意义下,提出基于词计算的上下文无关格值文法,证明由其生成的格值词语言关于并与连接运算封闭,及其与乔姆斯基范式文法等价.

浅议格值代数系统与格值上下文无关语言

引入格值语言及文法的概念,建立格值代数系统与格值上下文无关文法的转换法则,并证明二者的等价性.研究格值代数系统与格值上下文无关语言的关系,得到结论 :格值代数系统的强解的某个分量就是与该格值代数系统等价的格值上下文无关文法生成的格值上下文无关语言。

格值上下文无关语言的运算性质

在格值逻辑框架下给出上下文无关文法及上下文无关语言的概念,并研究了格值上下文无关语言在正则运算下的封闭性。