###
DOI:
Journal of Software:2003.14(1):23-27

基于量子逻辑的自动机和文法理论
邱道文
(中山大学,计算机科学系,广东,广州,510275;清华大学,计算机科学与技术系,北京,100084;清华大学,智能技术与系统国家重点实验室,北京,100084)
Automata and Grammars Theory Based on Quantum Logic
QIU Dao-Wen
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3075   Download 3059
Received:March 29, 2001    Revised:May 18, 2001
> 中文摘要: 初步建立了基于量子逻辑的自动机和文法理论的基本框架.引入了量子文法(称为l值文法),特别是证明了任意l值正规文法生成的语言(称为量子语言)等价于某种基于量子逻辑且含动作(的自动机(称为l值自动机)识别的语言,反之,任意l值自动机识别的语言等价于某l值正规文法生成的语言.建立了l值泵引理,并得到量子语言的判定性刻画.最后简要讨论了正规文法与量子文法(即l值正规文法)的关系.因此,为进一步研究更复杂的量子自动机(如量子下推自动机和Turing机)和量子文法(如量子上下文无关文法和上下文有关文法)奠定了基础.
Abstract:In this paper, a fundamental framework of automata and grammars theory based on quantum logic is preliminarily established. First, the introduce quantum grammar, which is called l valued grammars, is introduced. It is particularly showed that the language (called quantum language) generated by any l valued regular grammar is equivalent to that recognized by some automaton with e moves based on quantum logic (called l valued automata), and conversely, any quantum language recognized by l valued automaton is also equivalent to that generated by some l valued grammar. Afterwards, the l valued pumping lemma is built, and then a decision characterization of quantum languages is presented. Finally, the relationship between regular grammars and quantum grammars (l valued regular grammars) is briefly discussed. Summarily, the introduced work lays a foundation for further studies on more complicated quantum automata and quantum grammars such as quantum pushdown automata and Turing machine as well as quantum context-free grammars and context-sensitive grammars.
文章编号:     中图分类号:    文献标志码:
基金项目:(Supported by the National Grand Fundamental Research 973 Program of China under Grant No.G1998030509 (国家重点基础研究发展规划(973)); the National Natural Science Foundation of China for Distinguished Young Scholars under Grant No.69725004 (国家杰出青年科学基金); the Natural Science Foundation of Guangdong Province of China under Grant No.020146 (广东省自然科学基金); the Young Foundation of Zhongshan University of China under Grant No.35100-1131127 (中山大学青年基金) (Supported by the National Grand Fundamental Research 973 Program of China under Grant No.G1998030509 (国家重点基础研究发展规划(973)); the National Natural Science Foundation of China for Distinguished Young Scholars under Grant No.69725004 (国家杰出青年科学基金); the Natural Science Foundation of Guangdong Province of China under Grant No.020146 (广东省自然科学基金); the Young Foundation of Zhongshan University of China under Grant No.35100-1131127 (中山大学青年基金)
Foundation items:
Reference text:

邱道文.基于量子逻辑的自动机和文法理论.软件学报,2003,14(1):23-27

QIU Dao-Wen.Automata and Grammars Theory Based on Quantum Logic.Journal of Software,2003,14(1):23-27