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

Pushdown Automata and Context-Free Grammars Based on Quantum Logic

作　　者：韩召伟[1] 李永明[2] 

机构地区：[1]陕西师范大学计算机科学学院,陕西西安710062 [2]陕西师范大学数学与信息科学学院,陕西西安710062

出　　处：《软件学报》2010年第9期2107-2117,共11页Journal of Software

基　　金：国家自然科学基金No.10571112;陕西师范大学青年科技项目No.200701008~~

摘　　要：给出基于量子逻辑的下推自动机(l-VPDA)的概念,提出广义的子集构造方法,进而证明了一般的l-VPDA与状态转移为分明函数且具有量子终态的l-VPDA的等价性.利用此等价性,给出了量子上下文无关语言的代数刻画与层次刻画,并籍此证明了量子上下文无关语言关于正则运算的封闭性.最后,说明了量子下推自动机和量子上下文无关文法(l-VCFG)的等价性.In this paper, an orthomodular lattice-valued pushdown automaton （l-VPDA） is introduced. This paper also provides the means of general subset-construction, and further proves the fact that an l-VPDA can accept the same l-valued language by final states and by another l-VPDA, with crisp transition relation and quantum final states at the same time. By using these relations, this paper is able to establish some algebraic level characterizations of orthomodular lattice-valued context-free languages and also focuses on the closed properties of these l-valued languages in details under standard operative conditions. Finally, this paper presents that an arbitrary orthomodular lattice-valued context-free grammar （l-VCFG） are mutually equivalently constructed with a l-VPDA, respectively.

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

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