基于量子逻辑的下推自动机与上下文无关文法

摘要：

给出基于量子逻辑的下推自动机(l-VPDA)的概念,提出广义的子集构造方法,进而证明了一般的l-VPDA与状态转移为分明函数且具有量子终态的l-VPDA的等价性.利用此等价性,给出了量子上下文无关语言的代数刻画与层次刻画,并籍此证明了量子上下文无关语言关于正则运算的封闭性.最后,说明了量子下推自动机和量子上下文无关文法(l-VCFG)的等价性.

关键词：量子逻辑、正交模格、量子下推自动机、量子上下文无关语言、量子上下文无关文法

所属期刊栏目：21

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

资助基金：the National Natural Science Foundation of China under Grant No.10571112;the Youth Technology Project of Shaanxi Normal University of China under Grant No.200701008

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

页数：共11页

页码：2107-2117