题目：格值上下文无关文法的代数性质

文法理论是算法描述和分析,计算复杂性理论,可计算性等研究的基础, 它为计算理论提供了可靠的数学模型. 同样, 模糊(加权,量子)文法提供了一套研究和描述包含“模糊性”与“不精确性”自然语言的思路和方法,它必将为基于词的软计算理论提供可靠的形式基础. 而以往对文法的推广都是在满足分配律或者引入相应限制条件从而满足分配律的情形下进行的,但是分配律要求太强,一般代数结构不一定满足,因此在更一般的情形下,研究语言和文法具有非常重要的意义,其势必将拉近形式语言和自然语言之间的距离.
本文将在此方面做进一步的工作,特别地,我们定义了取值于一般格的上下文无关文法,研究了其对应的代数性质.主要结果如下:
1. 提出了格值上下文无关文法的概念,并研究了其具有的代数性质,给出格值逻辑意义下广义的格值子集构造方法,籍此
证明了任一l-VCFG与除一步推导为格值的(含格值信息)以外,其余推导都是经典推导的 l-VCFG之间的相互等价性;
2.提出格值上下文无关文法的两种范式文法,即格值上下文无关Chomsky范式文法和Greibach范式文法,并给出它们和格值上下文无关文法之间的相互等价性关系;
3. 详细研究了格值上下文无关语言的代数刻画,层次刻画以及对于正则运算的封闭性.