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

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

正规文法生成算法及其实现

本文给出了由正规式V生成有限自动机和正规文法的综合算法，并用PAS－CAL语言实现了该算法，具有很好的实用价值。     

自动机与正规式相互转换的方法

本文主要介绍基于编译器构造技术中的由正规表达式到最小化DFA的算法设计和实现技术,以及自动机转换正规式的方法。正规式与自动机理论以不同方式表达相同语言,两者相互转换在编译器构造过程中起至关重要的作用,也被广泛应用于计算机科学的各个领域。     

右线性文法与有限自动机等价性的一个新证明

迄今为止,左、右线性文法与有限自动机的等价性都是通过相互模拟构造来证明的。文章首先引入字母表上的右线性方程组及其最小解的概念,证明了最小解的存在性与有效可解性,描述了最小解的结构;其次通过右线性方程组及其最小解,证明了右线性文法与有限自动机的等价性。完全类似地,可以引入字母表上的左线性方程组及其最小解,并且证明左线性文...     

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

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

基于属性文法的正规式到NFA的转换

用状态转换图分析正规式时需要考虑的情况比较多,容易造成疏漏。且这种方法需要递归进行,多次扫描正规式,效率不高。该文采用SLR分析加属性文法只需一遍扫描就可以将正规式转存为NFA,效率要高得多。     

利用等价类构造有限状态自动机

一类语言由任意字母表上的某种进制的数字串构成，要求该语言中的所有数字串能够整除N；构造有限状态自动机识别该类语言是困难的，本文提出了根据等价类构造一类有限状态自动机的方法。该方法可以针对所有字母表和所有进制的数字串构成的语言，而且满足语言中的所有数字串能够整除任意正整数N。该方法实用、简便。     

Fuzzy正规集合与Fuzzy右线性文法的关系

在文献[1]的基础上,对Fuzzy正规集合和Fuzzy右线性文法之间的关系作了进一步的探讨,证明了Fuzzy正规集合的右线性可表示性,为进一步研究Fuzzy正规集合与Fuzzy有限状态自动机的关系提供了一种新方法.     

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

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

循环自动机的等价性

主要讨论了两个循环有限自动机的等价性与循环有限自动机的生成子之间的关系,在某些条件下给出了两个循环有限自动机等价的充分必要条件。     

由有穷自动机构造正则表达式的新算法

本文借助图论的理论，通过识别回路和不包含回路的由起始状态到终止状态的路径的方法，提出一种构造给定有穷自动机对应的正则表达式的新算法，并给出具体实例。     

多级文法在通用型中间件中的应用

在当今计算机技术发展的主流中，中间件技术是客户／服务器结构的关键技术.在对数据库专用中间件──RDA技术的深入研究后，针对它灵活性低、可扩充性差的特点，本文提出了适于构造基于通用型中间件的分布式环境的新技术──多级文法.实践证明将多级文法的技术引入中间件的构造大大提高了中间件的灵活性，增强了它的可扩充性，并使中间件本身具有了一些新的特点.目前，一个基于该多级文法的通用型中间件的原型系统已可在UNIX平台运行.     

汉字有穷自动机研究

为了更好地研究汉字信息输入系统，解决汉字输入的“瓶颈”问题，本文利用自动机理论，着眼于系统整体，建立了４种汉字信息输入处理系统的数学模型，引进了１－型，２－型，４－型自动机的概念，分别具体地给出了状态转移函数。     

环上线性有限自动机的可逆性的一些结果

本文证明了有单位元的有限交换环R上任何延迟t步(弱)可逆线性有限自动机皆有延迟t步线性(弱)逆的充分必要条件是环R满足条件: x(Ax=0→bx=0)→y(b=yA)我们还证明了对任何有单有限交换环R,R上输入、输出维数相同的延迟t步(弱)可逆线性有限自动机具有延迟t步线性(弱)逆.     

RECURRENT NEURAL NETWORKS AND FINITE AUTOMATA

This article studies finite size networks that consist of interconnections of synchronously evolving processors. Each processor updates its state by applying an activation function to a linear combination of the previous states of all units. We prove that any function for which the left and right limits exist and are different can be applied to the neurons to yield a network which is at least as strong computationally as a finite automaton. We conclude that if this is the power required, one may choose any of the aforementioned neurons, according to the hardware available or the learning software preferred for the particular application.     

二元弱可逆有限自动机延迟步数的分解

本文考虑二元严格延迟τ步弱可逆有限自动机Ｍ的延迟步数的分解问题。首先证明如果Ｍ强连通且所有状态的延迟步数不小于τ－１，则Ｍ一定能分解为一个延迟０步弱可逆有限自动机和一个τ阶延迟元。然后证明如果Ｍ所有状态延迟步数均不小于ｍ，那么Ｍ可以分解为一个严格延τ－ｍ步弱可逆有限自动机和一个ｍ阶延迟元。最后考虑了Ｍ可分解为一个严格延迟τ－１步和一个严格延迟１步弱可逆有限自动机的条件。     

关于模糊属性正则文法与可比较模糊属性自动机的一个注记

讨论了模糊属性自动机对由模糊属性正则文法产生的字符串进行识别的问题,建立了以标准字符串为核的隶属函数,利用该函数求出待识别串在标准串中各字符的隶属度,进而得到各字符与标准字符的差别,由此可求出待识别串与标准串差异最大的标准字符.进而对多个串的识别,利用格比较得到与标准串最相符的待识别串,从而提高了字符串的识别率和识别效果.     

关于弱可逆有限自动机延迟步数分解的两个结果

本文证明存在(任意元)延迟2步弱可逆有限自动机不等价于任何两个延迟1步弱可逆有限自动机的化合的任何子自动机。因而说明了不是对所有的弱可逆有限自动机,延迟步数都是可分解的,但对所有状态的延迟步数均为2的二元延迟2步弱可逆有限自动机,则分解是可行的。     

一种用于深度包检测的正则表达式分组算法

当前深度包检测算法通常需要将正则表达式转换为NFA或者DFA．但是随着网络带宽的不断增加．NFA和DFA状态占用的存储空间越来越大,极大地考验着系统的存储能力。为了应对这个问题．提出一种基于正则表达式相性的分组算法来对表达式进行分组,实验证明该算法能减少NFA和DFA状态的数量,提高匹配的效率。