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

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

识别在线手写汉字的模糊属性自动机

本文提出一种识别在线手写汉字笔划的模糊属性自动机,为汉字识别打下了基础.汉字 的笔划由笔段构成,利用笔段的长度信息,借助模糊信息处理方法,以不变嵌入原理为着眼点, 提出一种模糊属性文法及其相应的模糊属性自动机.这种文法在句法形式上是有限状态文法, 但语义规则中包含上下文的信息,其能力大大超过有限状态文法,相应的自动机能有效地识别 笔划.经对大量在线手写汉字的识别,表明了模糊属性自动机的实用性.     

文法推断研究的历史和现状

文法推断属于形式语言的归纳学习问题,它研究如何从语言的有限信息出发,通过归纳推断得到语言的语法定义.文章综述文法推断研究的历史和现状.首先阐述文法推断的理论模型,接着罗列上下文无关文法类及其非平凡子类、隐马尔可夫模型以及随机上下文无关文法的推断方法,最后简介文法推断的应用,并展望其发展趋势.     

格值下推自动机与格值上下文无关文法

引入了格值下推自动机、格值上下文无关文法及它们的语言的概念,证明了格值下推自动机以两种不同方式接受的语言类的等价性,研究了格值Chomsky范式文法、格值上下文无关文法及其派生所产生的语言的等价条件,揭示了在一定条件下,格值下推自动机接受的语言类与格值上下文无关文法产生的语言类的等价性,证明了有理格值语言均被格值下推自动机识别。     

基于规则与统计相结合的藏文文本自动查错方法研究

针对目前藏文文本自动查错方法的不足,该文提出了一种基于规则和统计相结合的自动查错方法.首先以藏文拼写文法为基础,结合形式语言与自动机理论,构造37种确定型有限自动机识别现代藏文字;然后利用查找字典的方法识别梵音藏文字;最后利用互信息和t-测试差等统计方法查找藏语词语搭配错误和语法错误等真字词错误,实现藏文文本的自动查错...     

形式语言与自动机中关于ε的一些问题

讨论了形式语言与自动机理论中关于空串ε的一些问题。分析了ε产生式对文法和语言分类的影响;从文法和有限状态自动机的角度讨论了开始符号S和开始状态q0的作用;提出了语言增加或减少ε句子的简单方法;研究了ε-NFA的ε状态转换函数的本质;提出了ε-NFA转换为NFA的新方法,即先将ε-NFA转换为文法形式,消除ε产生式和单产生式后得到正则文法,再将正则文法转换为NFA。并用实际例子进行了验证。     

形式语言中的几个算法问题

引导学生关注学科前沿,培养学生理论研究兴趣是高校教学的重要任务之一。笔者尝试在编译原理的教学中,引导学生思考关于计算的基本问题:如何描述问题,是否有问题没有算法,等等。文章从编译原理课程中形式语言与自动机部分内容中,引出字符串匹配、自动机等价测试、上下文无关文法等价测试等问题,证明有不可计算的问题,介绍和分析相关算法,引导学生理论研究兴趣,拓展课程学习深度和广度。     

量化上下文无关语言的代数性质

通过引入量化下推自动机与量化上下文无关文法的定义,研究了以两种不同方式接受语言的量化下推自动机等价性问题,证明了在可交换的双幺赋值幺半群上,量化下推自动机接受的语言与量化上下文无关文法生成的语言相同。     

结构化程序设计思想在形式语言与自动机理论中的体现

在形式语言与自动机理论课程中,文法与自动机的构造在本质上都与结构化程序设计的思想有着很强的联系。本文从具体例子出发,阐明了这种联系并将其上升到理论的高度。在教学实践中对这种联系的讲述,对学生理解和掌握文法和自动机的构造起到了非常积极的作用。     

格值树自动机与格值上下文无关树文法的等价性

本文将模糊树自动机和模糊上下文无关树文法的概念推广到格半群上。证明了在接受语言和生成语言的意义下,树自动机和上下文无关树文法是等价的。同时给出了构造正规形式的等价文法的方法。     

序言

形式语言的研究是计算机科学的一个重要领域。形式语言大约在1956年左右问世。那时Noam Chomsky给出一种文法的数学模型,这种文法与当时他所研究的自然语言有关。不久当程序设计语言ALGOL的语法由前后文无关文法定义时,便发现了,文法的概念对程序员是非常重要的。这样的研究自然会导致面向语法编译,并产生编译程序之编译程序的概念。自那以后的研究工作相当高涨,其结果致使形式语言和自动机理论之间的关系达到彼此不可分离的程度。时至     

译校者的话

《形式语言及其与自动机的关系》一书可看成数字电子计算机编译程序理论和语言理论之著作,着重讲形式语言与自动机的关系。 作者首先对什么是过程和算法作了一般定义。然后阐明了语言的两个生成系统,一个是文法,另一个是识别器,即常说的自动机。两者都是有穷表示,但说明的语言却都可以是无穷的。     

图文法综述

形式语言理论对计算机科学的发展起了重大的作用,作为对传统字符文法扩展的图文法的形式化研究,其重要意义是不言而喻的.本文在概述图文法的产生、发展和现状的基础上,着重介绍了从一维字符文法扩展到二维图文法所出现的新问题,以及在形式化处理上引出的新方法,其中最主要的是嵌入问题的解决、文法类型的划分和成员问题的判定.文中以目前较为流行的图文法为例,特别是一些典型的上下文无关和上下文相关的图文法,对上述的问题进行了深入的讨论,指出了现有方法中的一些不足之处,并展望了图文法今后值得研究的问题和方向.     

智能机器人系统的形式化建模

基于作者先前巳为智能机器人系统提出并建造成的一种新型结构模型──环递阶模型［１，２］，应用形式语言理论，首次将智能机器人系统整体形式化地建模成了一种上下文无关文法．     

智能机器人系统的形式建模

基于作者先前已为智能机器人系统提出并建造成的一种新型结构模型－－环递阶模型＾［１，２］，应用形式语言理论，首次将智能机器人系统整体形式化地建模成了一种上下文无关文法。     

计算科学的新领域：DNA计算（Ⅱ）

DNA计算是应用分子生物技术进行计算的新方法。从理论上研究DNA计算方法，有利于推动理论计算科学的发展。本系列文章应用形式语言及自动机理论技术，系统地探讨了DNA分子的可计算性及其计算能力。本文主要介绍DNA分子粘接计算模型的文法结构和计算方法，探讨了不同粘接计算模型的计算能力，并证明了DNA有穷自动机与正规文法的等价性。     

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

给出基于量子逻辑的下推自动机(e-VPDA)的概念,提出广义的子集构造方法,进而证明了一般的e-VPDA与状态转移为分明函数且具有量子终态的e-VPDA的等价性.利用此等价性,给出了量子上下文无关语言的代数刻画与层次刻画,并籍此证明了量子上下文无关语言关于正则运算的封闭性.最后,说明了量子下推自动机和量子上下文无关文法(e-VCFG)的等价性.     

正规文法与有限自动机的等价性研究

通过证明正规文法和有限自动机之间的等价性定理,给出正规文法和有限自动机之间的等价构造方法。     

RG识别关键技术研究

RG是形式语言中最典型的一类文法。主要讨论和分析了RG的一种识别分析方法,给出了该方法的主要算法及实现的关键技术。对文法识别和自动机生成有决定性的作用。可给后续研究提供支持。     

基于随机无穷自动机的多功能雷达辐射源识别方法

针对基于随机上下文无关文法（SCFG）建模的多功能雷达（MFR）辐射源识别问题,提出了一种基于随机无穷自动机（SISA）的MFR辐射源识别方法。在文法建模的基础上,对“水星”MFR控制模块文法产生式和系统特征文法产生式进行重新构造生成SCFG,利用SCFG构造随机无穷自动机作为识别器,从而实现对测量辐射源的识别。通过理论分析和实验仿真得出：该方法能实现对MFR辐射源的识别;在一定范围内,通过增加文法产生式个数,可以提高平均识别率,且识别性能优于通过SCFG构造的随机下推自动机（SPDA）。实验结果表明了该方法的正确性和有效性。