| 本文已被：浏览 4733次 下载 6247次 |
码上扫一扫！ |
|
|
| 基于量子逻辑的自动机和文法理论 |
|
邱道文1,2,3
|
|
1.中山大学,计算机科学系,广东,广州,510275;2.清华大学,计算机科学与技术系,北京,100084;3.清华大学,智能技术与系统国家重点实验室,北京,100084
|
|
| 摘要: |
| 初步建立了基于量子逻辑的自动机和文法理论的基本框架.引入了量子文法(称为l值文法),特别是证明了任意l值正规文法生成的语言(称为量子语言)等价于某种基于量子逻辑且含动作(的自动机(称为l值自动机)识别的语言,反之,任意l值自动机识别的语言等价于某l值正规文法生成的语言.建立了l值泵引理,并得到量子语言的判定性刻画.最后简要讨论了正规文法与量子文法(即l值正规文法)的关系.因此,为进一步研究更复杂的量子自动机(如量子下推自动机和Turing机)和量子文法(如量子上下文无关文法和上下文有关文法)奠定了基础. |
| 关键词: 量子逻辑 自动机 正规文法 形式语言 泵引理 |
| DOI： |
| 分类号: |
| 基金项目:(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 (中山大学青年基金) |
|
| Automata and Grammars Theory Based on Quantum Logic |
|
QIU Dao-Wen
|
| 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. |
| Key words: quantum logic automata regular grammar formal language pumping lemma |
