基于量子逻辑的自动机和文法理论

• 作者: 邱道文
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 量子逻辑 自动机 正规文法 形式语言 泵引理
• 年，卷（期）: 2003,（1）
• 所属期刊栏目: 理论计算机科学
• 页码范围: 23-27
• 页数: 5页
• 分类号: TP301
• 字数: 5228字
• 语种: 中文

摘要

初步建立了基于量子逻辑的自动机和文法理论的基本框架.引入了量子文法(称为l值文法),特别是证明了任意l值正规文法生成的语言(称为量子语言)等价于某种基于量子逻辑且含动作(的自动机(称为l值自动机)识别的语言,反之,任意l值自动机识别的语言等价于某l值正规文法生成的语言.建立了l值泵引理,并得到量子语言的判定性刻画.最后简要讨论了正规文法与量子文法(即l值正规文法)的关系.因此,为进一步研究更复杂的量子自动机(如量子下推自动机和Turing机)和量子文法(如量子上下文无关文法和上下文有关文法)奠定了基础.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	邱道文	中山大学计算机科学系	6	104	5.0	6.0