确定型有穷自动机状态极小化的研究

在树图分割法基础上,对确定型有穷自动机的极小化进行了研究.利用树图分割法,可以在状态的3次方时间内对确定型有穷自动机状态进行极小化.

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

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

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

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

一种基于有穷状态自动机的二维浅海声线追踪方法

给出了一种二维的浅海声线追踪方法,解决了声线的反射、折射、全反射等问题并快速地找出声线的路径。对于单步的声线追踪,声速剖面假定为水深的函数,利用Snell定律进行单步求算。用有穷状态自动机对浅海的声线追踪建模,给出了浅海声线追踪内在的状态及状态转移分析。同时,给出了本征声线搜取的方法。最后通过对特定声速剖面情况的数值解值和解析解值进行比较,验证了该方法的正确性,并且讨论了应用该方法应该注意的问题和方法中还有待解决的问题。数值仿真实验结果表明,这种方法能够追踪浅海声线路径,其数值解精度达10-4.该方法在匹配场层析、目标跟踪定位和其它领域的射线跟踪有着应用前景。

一种基于确定型有穷自动机的动物识别系统的设计方法

提出了一种新的动物识别系统的设计方法。通过对有穷自动机理论与动物识别系统进行分析,建立了一个基于动物特征的确定型有穷自动机的模型.该模型描述了当输入一个动物特征值后,自动机的状态将发生转移,当输入的动物特征值充足时,即可识别出动物的种类.最后,根据这种模型设计出了动物识别系统,并上机进行了实现。

基于确定有限状态自动机的改进多模式匹配算法研究

针对网络入侵检测系统的一般问题,在详细分析现存单模式与多模式匹配算法的基础上,将AC算法里的DFSA方法与单模式匹配算法BMH的思想相融合,以求取优化检测效率为目标,提出一种基于确定有限状态自动机的改进多模式匹配算法。该算法特别适合在大字符集文本串中查找小字符集模式串。将该改进多模式匹配算法应用到Snort入侵检测过程中,针对处理结果进行科学评价。通过实例的应用,验证了该改进算法的可行性和高效性。

基于有穷状态自动机浅海声场仿真研究

提出一种用有穷状态自动机研究浅海声场的方法。应用Snell定律对单步的声线传播进行研究,分析了浅海声场内在的状态及状态转移特性,推导出浅海声场的有穷状态自动机。步长根据实验精度要求设定,仿真实验表明步长越小,精度越高,计算量越大。为了减小运算量,本征声线通过两次追踪不同步长的方法获得。数值仿真结果证明了该方法的可行性,其精度可以达10-4。该方法可望应用到光学和地震学等领域的射线传播研究中。

基于非确定有穷自动机的网络入侵容忍系统研究

入侵容忍技术是继防火墙、存取控制、入侵检测技术之后的网络信息安全技术。当一个网络系统遭受非法入侵后,入侵容忍系统仍能及时自我诊断、恢复和重构,并能为合法用户提供所需的全部或者降级的服务。本文依据非确定性有穷自动机理论,模拟计算机受到攻击时入侵容忍系统的工作过程,为入侵容忍技术的发展提供了一种方法。

基于改进BM算法的确定型有穷自动机的设计

通过对有穷自动机理论与BM算法进行分析,设计了一个基于改进BM算法的确定型有穷自动机的模型.该模型描述了向基于改进BM算法的确定型有穷自动机输入文本字符串,自动机输出TRUE,说明文本串中存在与模式串相匹配的字符;自动机输出FALSE,说明文本串中不存在与模式串相匹配的字符串.并给出了对比实验及分析.

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

运用KMP算法的思想生成确定型有穷自动机的转移函数 ,使得确定型有穷自动机可以接受以输入串 (以 0和 1组成 )

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

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

基于非确定型有限状态自动机的基因逻辑网络模型

阐述近年来基因网络逻辑行为的新模型———有限状态自动机模型,针对该模型的局限性,本文提出了改进,建立非确定型自动机模型,以描述网络行为的非确定型,适应基因网络的异常表达需要.

确定有穷自动机的最小化问题探讨

本文针对DFA最小化时可能遇到的各种情形，给出最小化的通用算法，并通过具体实例加以验证。此算法有利于学生对编译原理课程中DFA最小化的学习和理解，同时让学生进一步了解此知识点在其他问题求解中的应用。

非确定有穷自动机在盲文转码中的应用

对盲人使用的计算机交互技术进行研究是很有意义的工作。盲文字库缺少国际标准和不同公司的盲文字库不兼容造成了很多难题。将盲文用汉字点位编码表示,能摆脱盲文字库的束缚。用不确定有穷自动机描述盲文与汉字点位编码的转换过程,再用逆序拆分子集法对其确定化。经测试系统的转码正确率达到100%,从而实现盲文与机器无关,使得盲人使用计算机更方便。

基于有穷自动机的自然语言状态转换

针对Robocup自主机器人比赛中,机器人进攻和防守状态、动作转换延迟问题,采用一种基于有穷自动机模型的自然语言状态转换方法,把机器人、环境等自然语言信息抽象成形式化的符号和状态,并转化为有穷自动机输入符号.通过设定状态转移函数、字母表规则、无差别地完成各种状态转换过程.研究结果表明:该方法能有效地完成自然语言状态下的机器人状态、动作间的转换,具有较好的实时性和可靠性.

基于有穷状态自动机原理的粉状物料运输车智能卸料控制程序

控制程序是粉状智能物料运输车完成自动卸料过程的关键,控制程序设计的好坏决定卸料过程能否顺利完成。针对新型粉状物料运输车智能卸料控制器,采用基于消息传递机制和有限状态机原理的多分支结构,程序结构简单清晰,容易编写、调试、功能扩展。

视觉导航有穷自动机在自然语言状态中的应用

室内移动机器人自主导航是一系列自然语言状态与动作转换结果,有效地控制和描述机器人状态和动作转换是自主导航过程的关键。本文首先利用视觉传感器获取障碍物YUV色彩空间信息,采用区域增长法识别障碍物连通域,将机器人状态以及控制指令转化为抽象的形式符号并建立状态转移函数,进而建立基于视觉导航机器人有穷自动机模型。实验结果表明,该方法能平滑、准确地完成自然语言状态下的机器人自主导航过程,具有较高的实时性和鲁棒性。

CAD系统中嵌套有穷状态自动机的设计与实现

基本CAD系统中都要用到有穷自动机,在一般的CAD系统中,通常用switch、case语句来设计相应的状态图,这样做不但在状态复杂时逻辑上容易出错,而且使多个开发者无法同时开发和调试自动机的几个子模块,一定程度上限制了开发并行性和进度,非嵌套有穷自动机的设计基本上模仿状态图的逻辑设计,让状态图的设计者可以像画状态图一样直观地设计自动机,增加了逻辑上的清晰性。在此基础上改造的嵌套有穷自动机有效地实现了多个开发者对某一自动机子功能的并行设计和单元测试,能有效地提高开发效率。

基于紧凑型有穷自动机模型的告警相关处理

在网络管理领域 ,告警相关 (Alarm Correlation)是取代简单告警过滤机制的一种全新故障管理策略 .通过在非确定型有穷自动机 (ndfa)的定义中引入状态基 (State Cardinality)的概念 ,本文首先给出紧凑型有穷自动机 (cfa)的定义 ,然后提出了基于紧凑型有穷自动机的告警相关处理模型并进行了详尽的描述 .在一个电信管理网 (TMN)的故障管理子系统中应用该模型对大量的告警信息在时间上和空间上进行告警相关处理 .仿真结果表明 ,基于紧凑型有穷自动机的告警相关处理模型的算法实现具备简单、高效、实用和实时的特点 。

确定有限自动机最小化算法的并行处理

对有限自动机模型最小化做了深入分析,提出了一种基于可区分状态表结构的并行最小化算法,以实例详细描述了算法并行处理过程并验证其算法的可行性。