共查询到19条相似文献,搜索用时 93 毫秒
1.
Fuzzy树自动机的等价性 总被引:2,自引:0,他引:2
柏明强 《四川师范大学学报(自然科学版)》2009,32(1)
在给出模糊树自动机概念的基础上,讨论了模糊树自动机与传统字符自动机、模糊有限自动机相类似的性质,即指确定性模糊树自动机与非确定性的模糊树自动机的等价性、FNBTA与FNTTA 等价,及FDBTA和FNBTA等价;这为模糊树自动机的进一步研究奠定了基础. 相似文献
2.
有穷自动机中的等价性与等价归并算法 总被引:7,自引:0,他引:7
通过引入等价性原则,简化了对正则语言判定的步骤,并在有限自动机的状态集上引入等价关系,利用等价归并算法将给定的自动机中的等价状态进行归并,生成与其等价的最小自动机。 相似文献
3.
关于概率自动机的等价性与极小化问题 总被引:6,自引:0,他引:6
本文给出了两概率自动机按顺序初始等价的充要条件,证明了初始等价的概率自动机的基矩阵秩必相等及判定极限极小概率自动机的一个充要条件.同时也更正了[1]中的一个错误。 相似文献
4.
王晓峰 《广西民族大学学报》2008,14(3)
引入了等价性原则,定义等价关系的商集合∑*/~B,通过对商集合的有限性判断,来判定正则语言,大大简化了正则语言判定的步骤,并在有穷自动机的状态集上引入了等价关系,对等价状态进行压缩,构造出与其等价的最小有穷自动机,同时降低了有穷自动机状态的复杂性. 相似文献
5.
张树华 《兰州大学学报(自然科学版)》1987,(2)
凡多项式时间等价于图同构检验的问题称为同构完全问题.本文证明了,强连通自动机同构检验问题、自动机强同构检验问题、自动机自同构问题和自动机的自同构群的阶问题是同构完全的。 相似文献
6.
《山东大学学报(理学版)》2019,(5)
引入了L-值下推自动机的概念,讨论了L-值下推自动机按2种不同方式所接受的语言类的等价性,并指出了它能识别L-值正则语言。利用广义的子集构造方法,证明了一般的L-值下推自动机与状态转移为分明函数且具有L-值终态的L-值下推自动机的等价性。通过此等价性,给出了L-值上下文无关语言的代数刻画和层次刻画,并证明了L-值上下文无关语言关于正则运算的封闭性。另外,提出了L-值上下文无关文法的概念,给出了与之等价的且带有经典开始符的L-值上下文无关文法。借此等价关系,讨论了L-值下推自动机与L-值上下文无关文法是等价的,并说明了在完备剩余格值逻辑意义下,可采用最左派生、最右派生、Chomsky范式或者Greibach范式中的任何一种来生成L-值上下文无关语言。 相似文献
7.
作者讨论了有限态确定模糊自动机FDA与它相应的模糊语言以及FDA与其它自动机的等价性.这就为任何自动机的抽取和应用奠定了理论基础. 相似文献
8.
9.
介绍了一种基于词计算的一类新的Fuzzy有限自动机,这种自动机的输入和输出分别由输入和输出字母表的Fuzzy子集串代替,定义了它的最小形式,得到这种新的Fuzzy有限自动机M都存在一个与之等价的最小Fuzzy有限自动机Mm。 相似文献
10.
有限自动机放在粗糙集的范畴中来研究,它的各个状态对应粗糙集论域中的每个对象,每个输入符号为一个等价关系。从粗糙集的角度,利用对论域进行知识划分的方法,每次产生新的等价类,直到每个等价类都不能划分为止,从而得到最小化的有限自动机。与已有的研究方法不同,该方法以粗糙集理论为工具,为有限自动机最小化方法研究提供了新的思路。 相似文献
11.
张丽 《宁夏大学学报(自然科学版)》2012,33(2):148-151
自动机状态极小化是寻求状态数较少的自动机,使其与原自动机接受相同的语言.确定型有穷状态自动机(DFA)极小化问题在平方时间内可解,通过状态集上引入等价关系导出的商自动机即为接受相同正则语言的极小化自动机.而非确定型有穷状态自动机(NFA)极小化问题尚未找到有效算法.尽管NFA可以转化为DFA且接受的语言不变,但可能会出现状态数指数级增加.从语言B可以构造一个接受自己的子语言自动机,同态压缩映射子语言自动机为最终系统,从而为接受语言B的极小化自动机. 相似文献
12.
在研究了汉字有穷自动机可以表示的语言基础上,引进了最小状态汉字有穷自动机和可区分状态的概念,并利用汉字有穷自动机间的等价性和可区分状态的性质,给出了一种最小化算法,实验证明,此算法优于最小化汉字有穷自动机算法. 相似文献
13.
定义了偶正则表达式,证明了PRE和双读头自动机的等价机,为线性语言提供了一种新的有穷表示。 相似文献
14.
首先简介了时间自动机、时钟区域、区域等价、时钟带的概念.利用时钟带,可以将时间自动机的无穷状态空间转化为有穷.实时系统的绝大多数安全性和部分活性可以通过可达性分析算法来验证.然而,当系统时钟个数较多时,用DBM存储时钟带,会造成内存空间的很大耗费.该文提出了用邻接表存储时钟带,给出了改进的算法,并对算法的空间复杂度作了分析.实验表明,当时钟个数大于5时能节约很大的内存空间,从而在一定程度上缓解了状态爆炸. 相似文献
15.
主要讨论了Moore自动机(弱)可逆的一些性质,并给出了当|S|=|Y|时,Moore自动机(弱)可逆的充要条件。 相似文献
16.
基于时间自动机的验证工具已被广泛应用于实时系统模型验证。信号自动机为一类实时系统建立了比时间自动机更适合的模型,但是它还不能用于实际的实时系统模型验证,因为没有验证算法可用。把信号自动机验证问题归约到了时间自动机验证问题:证明了两种自动机具有相同的识别语言能力,证明了二者具有双向模拟关系,并在此基础上提出了线性的互模拟算法。把互模拟算法和已有的时间自动机验证算法结合起来,就得到了信号自动机的验证算法,从而解决了对信号自动机模型的验证问题。 相似文献
17.
18.
19.
阐述了最近几年来国外基因网络系统逻辑行为的研究新进展——基于有限状态自动机模型的方法,针对该方法的局限性,提出了一种基于有限运行时间自动机的基因网络模型,以描述网络行为的时间约束. 相似文献