非确定型有穷自动机的极小化

利用自动机状态集上的等价关系对自动机的状态集进行极小化, 从而得到与原自动机功能等价的极小化自动机. 通过两台确定型有穷自动机（DFA）的连接, 构造一台非确定型有穷自动机（NFA）. 利用这两台确定型有穷自动机状态集上的等价关系, 可以构造这台非确定型有穷自动机状态集上的等价关系, 从而对这台非确定型有穷自动机进行极小化. 结果表明这台非确定型有穷自动机的极小化自动机的状态复杂 度, 不大于对那两台确定型有穷自动机的极小化自动机进行连接得到的非确定型有穷自动机的状态复杂度; 并且自动机在等价关系基础上进行极小化时不改变识别语言.     

关于确定有穷自动机最小化算法的注记

《程序设计语言编译原理》给出了确定有穷自动机(以下简称为DFA)最小化的算法.步骤1 构造DFA M 状态集S的分划Ⅱ.该分划是由若干个不相交的状态子集所组成,并且任何不同的两子集的状态都是可区别的,而同一子集中的任何两个状态都是等价的.其构造算法如下:BEGIN     

基于前序关系的非确定型有穷自动机极小化算法

为了减少非确定型有穷自动机(non-deterministic finite automata,NFA)的状态数,引入前序关系,并以图论为工具,将NFA的转移图看作一个带有标记的有向图,给出了NFA极小化的一个新方法。与现行的利用归并等价状态来极小化NFA的算法相比,该方法可以使得NFA在接受语言的能力等价的前提下,状态数得到进一步的减少。     

交替ω—有穷自动机接受ω—语言能力的研究

本文研究了交替ω－有穷自动机关于接受条件Ｚ１和Ｚ２接受ω＝语言的能力,并且与交替ω－有穷自动机关于另外接受条件接受ω－语言的能力进行了比较,从而得出了下面主要结果：ＡＣ１＝ＡＺ１＝Ａ６２Ｚ１＝Ａ＾ＳＺ２＝ＡＺ２。     

关于ω-有穷自动机的接受条件

关于ω－有穷自动要的接受条件的研究,旨在揭示ω自动识别语言的能力以及对语言类作进一步的划分,到目前为止ω－自动机的接受条件已有六种,本文给出了一些新形式的接受条件并且研究了ω－有穷自动机在这些接受条件下接受ω－语言的能力。     

一种非确定型有穷自动机的极小化方法

自动机状态极小化是寻求状态数较少的自动机,使其与原自动机接受相同的语言．确定型有穷状态自动机（DFA）极小化问题在平方时间内可解,通过状态集上引入等价关系导出的商自动机即为接受相同正则语言的极小化自动机．而非确定型有穷状态自动机（NFA）极小化问题尚未找到有效算法．尽管NFA可以转化为DFA且接受的语言不变,但可能会出现状态数指数级增加．从语言B可以构造一个接受自己的子语言自动机,同态压缩映射子语言自动机为最终系统,从而为接受语言B的极小化自动机．     

确定有穷状态自动机最小化算法的三点说明

确定有穷状态自动机最小化可提高词法分析程序的效率.本文简述了最小化的概念、算法,从基本概念出发分析了该算法初始分划如何构造,及在状态无后继和全部由终止状态构成时这两种特殊情况下的解决对策,并对原算法做了进一步的细化.     

正则语言非正则运算的封闭性

本文用构造的方法严格证明了识别正则语言三种非正则运算的确定型有穷自动机的存在性，进而得出正则语言类在非正则运算“∩”、“-”以及“ ”下的封闭性的结论，并具体给出识别三类语言运算的确定型有穷自动机模型．     

有穷自动机的数字电路故障定位方法

用有穷自动机确定数字电路故障定位方法,从而可得到故障定位向量构成的语言正则性及其性质的一些实用结果     

基于KMP算法的确定型有穷自动机的设计

运用KMP算法的思想生成确定型有穷自动机的转移函数，使得确定型有穷自动机可以接受以输入串（以0和1组成）为子串的任意字符串。     

有穷自动机在车辆管理系统开发中的应用

利用有穷自动机理论对"企业车辆管理"的生命周期状态转化进行了形式化描述.通过分析车辆管理的流程,得到了车辆管理所涉及的各项业务流程,并对各项业务进行了说明,使得车辆管理的业务流程更加清晰.     

连接型自动机的极小化及其复杂性

通过定义确定型有穷自动机在状态集上的等价关系,可以构造一类非确定型有穷自动机在状态集上的等价关系,利用这个等价关系可以对这类非确定型有穷自动机进行极小化。     

格值模糊自动机及对应语言的分级

为了探讨格值模糊自动机等价的条件,采用对偏序格半群加以限制的方法,将格值模糊有限自动机划分为确定的、序列型的、无歧义的、有限歧义以及无限歧义自动机这几种不同的类型,得到这几类自动机接受语言之间的关系为L-DFA■L-Seq■L-NAmb■L-FAmb■L-Reg;当偏序格半群非局部有限时,关系为L-DFAL-SeqL-NAmbL-FAmbL-Reg;当偏序格半群局部有限时,关系为L-DFA=L-Seq=L-NAmb=L-FAmb=L-Reg.     

正则表达式与有穷自动机等价性在Isabelle/HOL中的形式化

针对正则表达式和有穷自动机,在机器辅助定理证明系统Isabelle/HOL中进行了形式化描述。通过对语言、正则表达式、确定和不确定有穷自动机在Isabelle/HOL中建立模型,定义了它们之间的相互转换函数并证明了这些函数的正确性,从而验证了正则表达式和有穷自动机在描述能力上的等价性,即:在同一有限字母表下,对任意正则表达式,都存在一个有穷自动机,使得二者描述的语言相同;反之亦然。通过分析与证明,表明采用机器辅助定理证明系统,对计算理论传统核心领域之一的自动机理论进行分析和证明是可行的。     

汉字有穷自动机的优化及相关算法研究

在研究了汉字有穷自动机可以表示的语言基础上,引进了最小状态汉字有穷自动机和可区分状态的概念,并利用汉字有穷自动机间的等价性和可区分状态的性质,给出了一种最小化算法,实验证明,此算法优于最小化汉字有穷自动机算法.     

有穷自动机在CRC码生成中的应用及CRC码的布尔函数的性质

文章给出了CRC码中所含1的个数与生成多项式的关系的一个性质.在此基础上,利用CRC码对应的有穷自动机变换,使CRC码的生成可由有穷自动机很容易并自动地生成.同时探讨了CRC码的布尔函数的一些性质.     

接受超线性语言的有穷转向的pda构造法和超线性语言秩的性质

S·Ginsburg和E·H·Spanier定义了有穷转向的pda,理论上证明了有穷转向的pda接受超线性语言类,给出了超线性语言秩的一些性质.本文将设计由超线性文法直接构造相应的有穷转向pda的方法,对超线性语言秩的性质作进一步的讨论,进而定义极小秩文法,给出判定极小秩文法的一个必要条件.     

确定型有穷状态自动机的同态压缩

对于确定型有穷状态自动机(DFA),通过定义状态集上的等价关系≈Q,借助于等价关系,可以在平方时间内构造出接受相同语言的极小化自动机.本文在DFA之间引入同态关系,证明了同态压缩下DFA接受相同语言.     

FDA与模糊语言及与其它自动机的等价性

作者讨论了有限态确定模糊自动机FDA与它相应的模糊语言以及FDA与其它自动机的等价性.这就为任何自动机的抽取和应用奠定了理论基础.