|
| 摘要: |
| 给出基于量子逻辑的下推自动机(e-VPDA)的概念,提出广义的子集构造方法,进而证明了一般的e-VPDA与状态转移为分明函数且具有量子终态的e-VPDA的等价性.利用此等价性,给出了量子上下文无关语言的代数刻画与层次刻画,并籍此证明了量子上下文无关语言关于正则运算的封闭性.最后,说明了量子下推自动机和量子上下文无关文法(e-VCFG)的等价性. |
| 关键词: 量子逻辑 正交模格 量子下推自动机 量子上下文无关语言 量子上下文无关文法 |
| DOI： |
| 分类号: |
| 基金项目:Supported by 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 (陕西师范大学青年科技项目) |
|
| Pushdown Automata and Context-Free Grammars Based on Quantum Logic |
|
HAN Zhao-Wei, LI Yong-Ming
|
| Abstract: |
| In this paper, an orthomodular lattice-valued pushdown automaton (e-VPDA) is introduced. This paper also provides the means of general subset-construction, and further proves the fact that an e-VPDA can accept the same l-valued language by final states and by another e-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 (e-VCFG) are mutually equivalently constructed with a e-VPDA, respectively. |
| Key words: quantum logic orthomodular lattice orthomodular lattice-valued pushdown automata orthomodular lattice-valued context-free language orthomodular lattice-valued context-free grammar |
