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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基于等价关系的有穷自动机最小化方法

主要介绍了有穷自动机的基础知识，研究了有穷自动机的等价性，并在确定型有穷自动机的状态集上引入等价关系，给出了自动机的最小化过程。利用等价归并算法，可以将某一给定的确定型有穷自动机状态集上的等价状态归并掉．生成与其等价的最小化的确定型有穷自动机。

基于自动机理论的PDF文本内容抽取

现有的从PDF文档抽取文本内容的方法(如PDFBox类库采用的方法)处理速度较低,无法满足高速网络中内容分析的需求,也不能对网络中部分到达的PDF数据包进行流式的处理。为此,提出了基于自动机理论的PDF文本内容抽取方法。该方法通过建立具有层次的关键字自动机,可以快速地抽取完整PDF文档和不完整PDF文档中的文本内容。在中文和英文PDF文档数据集下的实验结果表明,基于自动机理论的PDF文本内容抽取方法耗时仅为PDFBox方法的17%～37%。

多态自动机在字符串搜索及统计时的应用

多态自动机较之有穷自动机有更强的计算功能和对算法的描述功能,所以在计算理论和学习理论中有相当地位.本文首先简要地介绍了多态自动机,然后利用多态自动机的计算功能给出了一种搜索算法,此算法可以完成字符串的搜索和统计功能.文章对此算法的复杂度进行了分析,该算法的复杂度是多项式的,并且对此算法添加一些辅助部分也可以完成搜索网络资源的功能.此算法在计算机上也很容易实现.

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

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

非确定模糊有穷自动机的ε-语言逼近

在max-*复合推理下引入了非确定模糊有穷自动机的概念,其中*是t-模运算。为了比较2个非确定模糊有穷自动机的行为,借助于[0, 1]上的一个实数ε,定义了2种ε-语言逼近,讨论了它们之间的关系。证明了非确定模糊有穷自动机和模糊有穷自动机之间是0-弱语言逼近的,即二者可以接受相同的模糊语言。此外,还讨论了2种ε-语言逼近的一些代数性质,特别地给出ε-语言逼近在并运算、*运算以及连接运算下的性质。最后,分析了ε-语言逼近的鲁棒性。

一种将NFA到最小化DFA的方法

词法分析是编译程序重要阶段,有效的词法分析可提高编译程序的效率。本文提出用子集方法完成NFA到DFA并使用树型分割法实现DFA到最小化DFA的化简。

一种新的DFA状态最小化算法

提出了一种基于状态转换矩阵的适合计算机实现的DFA状态最小化算法,在计算等价状态过程中,通过记录扫描过程中发现的具有相同输入字符和相同转换状态的状态判定链表,算法可以用一遍扫描和与传统算法相近的存储空间实现DFA状态的最小化。与传统的DFA状态最小化算法相比,该算法具有较好的时间复杂度和相同的空间复杂度。

基于改进的Trie树和DFA的敏感词过滤算法

通过对文本内容中敏感词过滤方法及相关技术的研究,提出了一种基于改进的Trie树和DFA的敏感词过滤算法,解决了敏感词过滤技术中的人工干扰、分词障碍等关键问题,提高了文本中敏感词过滤的准确性和有效性。提出的算法包括三个步骤:基于排列组合的数学原理对中文词向中拼混合词进行扩充;采用改进的Trie树结构来存储DFA的所有状态,构建敏感词树;根据构建的敏感词树结构以及采用最小匹配规则对文本内容中的敏感词进行检测和过滤。通过分析得到构建敏感词树算法的时间复杂度为O(n×len),敏感词检测及过滤算法时间复杂度为O(L)。实验结果表明,本算法其查准率为100%,查全率约为87%~100%。

基于决策树和DFA的老挝文敏感信息过滤算法

通过对老挝文语言特点的分析,提出一种基于确定有穷自动机和决策树的老挝文敏感信息过滤算法。将老挝文进行词汇划分和编码化处理,合理地解决老挝文与汉语书写上的差异性以及计算机读取存储出现乱码的问题;结合决策树的特点,构建老挝文敏感信息决策树,该树不依赖于词典,且可以实现实时更新;基于确定有穷自动机模型实现了老挝文敏感信息的检测和过滤,同时也实现了实时报警。实验表明,该过滤算法针对老挝文有较高的工作效率,同时也取得了较好的查全率和查准率。

基于网络文本信息的敏感信息过滤算法

为实现对网络敏感信息的检测和过滤,提出一种基于确定有穷自动机的改进算法ST-DFA(swift tree DFA)。对传统的DFA过滤算法进行改进,不再依赖敏感信息语料库,只须建立一次敏感信息决策树,即可实现对网络信息的多次过滤;当敏感词语料库发生更新时,可以实现对敏感词的决策树的实时更新。实验结果表明,ST-DFA算法有较高的工作效率,适合当下对互联网敏感信息的检测与过滤。

深度包检测中一种高效的正则表达式压缩算法

提出一种基于确定的有穷状态自动机(deterministic finite automaton,简称DFA)的正则表达式压缩算法.首先,定义了膨胀率DR(distending rate)来描述正则表达式的膨胀特性.然后基于DR提出一种分片的算法RECCADR(regular expressions cut and combine algorithm based on DR),有效地选择出导致DFA状态膨胀的片段并隔离,降低了单个正则表达式存储需求.同时,基于正则表达式的组合关系提出一种选择性分群算法REGADR(regular expressions group algorithm based on DR),在可以接受的存储需求总量下,通过选择性分群大幅度减少了状态机的个数,有效地降低了匹配算法的复杂性.

基于UML协作图和DFA的测试用例生成方法研究

UML协作图能够描述对象之间动态的交互关系及对象之间消息传递的过程,根据协作图中的消息流和控制流可以获取有用的场景模型并生成测试用例。本文在研究UML协作图和确定有穷自动机(DFA)之间对应关系的基础上,提出一种将UML协作图转换为DFA,再从DFA中提取测试场景生成测试用例的方法,并将该方法应用于实际项目的测试用例生成。最后,通过对结果进行数据对比和分析,说明该测试用例生成方法的有效性。