共查询到19条相似文献,搜索用时 265 毫秒
1.
为了减少非确定型有穷自动机(non-deterministic finite automata,NFA)的状态数,引入前序关系,并以图论为工具,将NFA的转移图看作一个带有标记的有向图,给出了NFA极小化的一个新方法。与现行的利用归并等价状态来极小化NFA的算法相比,该方法可以使得NFA在接受语言的能力等价的前提下,状态数得到进一步的减少。 相似文献
2.
Fuzzy树自动机的等价性 总被引:2,自引:0,他引:2
柏明强 《四川师范大学学报(自然科学版)》2009,32(1)
在给出模糊树自动机概念的基础上,讨论了模糊树自动机与传统字符自动机、模糊有限自动机相类似的性质,即指确定性模糊树自动机与非确定性的模糊树自动机的等价性、FNBTA与FNTTA 等价,及FDBTA和FNBTA等价;这为模糊树自动机的进一步研究奠定了基础. 相似文献
3.
在研究了汉字有穷自动机可以表示的语言基础上,引进了最小状态汉字有穷自动机和可区分状态的概念,并利用汉字有穷自动机间的等价性和可区分状态的性质,给出了一种最小化算法,实验证明,此算法优于最小化汉字有穷自动机算法. 相似文献
4.
5.
王晓峰 《广西民族大学学报》2008,14(3)
引入了等价性原则,定义等价关系的商集合∑*/~B,通过对商集合的有限性判断,来判定正则语言,大大简化了正则语言判定的步骤,并在有穷自动机的状态集上引入了等价关系,对等价状态进行压缩,构造出与其等价的最小有穷自动机,同时降低了有穷自动机状态的复杂性. 相似文献
6.
7.
确定有限自动机的逻辑形式定义 总被引:3,自引:1,他引:2
通过分析确定有限自动机状态转换函数的内在含义,引入有关的原子命题,得到确定有限自动机的逻辑形式定义并证明了状态转换函数表示与逻辑表示之间的等价性. 相似文献
8.
关于概率自动机的等价性与极小化问题 总被引:6,自引:0,他引:6
本文给出了两概率自动机按顺序初始等价的充要条件,证明了初始等价的概率自动机的基矩阵秩必相等及判定极限极小概率自动机的一个充要条件.同时也更正了[1]中的一个错误。 相似文献
9.
曹勇 《中山大学学报(自然科学版)》1985,(2)
文献[1]讨论了二类模糊自动机的等价性,但其证明过程有错误.本文给出证明,并提出了第三类模糊自动机,它与[1]中二类等价.记R=[0,1].定义1 一个最大积(max-product)自动机(MA),是一个五元组M=(Σ,S,P,h,g)这里Σ和S 是有限非空集,P 是S×Σ×S 到R 的函数,h 和g 是S 到R 的函数.在这定义里,Σ和S 分别表示输入字符集和状态集,P(s′|μ,s)表示M 的当前状态为s,输入字符为μ,其下一状态为s′资格函数.h(s)和g(s)分别表示M 的状态s 为开始状态和终止状态的资格函数. 相似文献
10.
使用自动机理论建立了一个用于分析实时调度问题的、可化简归并的形式化方法。通过分析单个任务的状态变化过程来构造实时系统的自动机。对自动机的状态进行化简和归并,大大降低了讨论实时调度问题的复杂度。以优先级上限协议为例构造了确定有穷自动机并使用该自动机证明了优先级上限协议的性质。 相似文献
11.
非确定型有穷自动机的极小化 总被引:1,自引:0,他引:1
利用自动机状态集上的等价关系对自动机的状态集进行极小化, 从而得到与原自动机功能等价的极小化自动机. 通过两台确定型有穷自动机(DFA)的连接, 构造一台非确定型有穷自动机(NFA). 利用这两台确定型有穷自动机状态集上的等价关系, 可以构造这台非确定型有穷自动机状态集上的等价关系, 从而对这台非确定型有穷自动机进行极小化. 结果表明这台非确定型有穷自动机的极小化自动机的状态复杂
度, 不大于对那两台确定型有穷自动机的极小化自动机进行连接得到的非确定型有穷自动机的状态复杂度; 并且自动机在等价关系基础上进行极小化时不改变识别语言. 相似文献
12.
13.
MA Haitao HAO Zhongxiao ZHU Yan 《武汉大学学报:自然科学英文版》2006,11(5):1325-1329
The problem of document rewriting is a fundamental problem in active XML(AXML) data exchange and usually has a higher complexity. Prior work was focused on string automaton theory. This paper tries to solve it by using tree automaton. More precisely, the paper firstly defines a new tree automaton, active XML tree automaton (AXTA), which can efficiently represent the set of AXML documents produced by an AXML document or AXML document schema. And then, an algorithm for constructing AXTA automaton is also proposed. Finally, a polynomial time(PTIME) determining algorithm for AXML document rewriting is presented based on AXTA automaton. 相似文献
14.
复杂数据类型验证是XML文档验证的主要内容,是检查XML文档结构是否符合模式规则的关键.根据Schema规范中复杂数据类型的描述和自动机理论,提出了一种称为模式自动机的数据结构,讨论了将XML复杂数据类型结构转换成模式自动机的方法,并设计了用来验证文档结构的算法.使用模式自动机验证算法可以全面地发现XML文档中的结构错误并准确地给出相应的错误信息,在实际应用中具有很高的效率. 相似文献
15.
基于混合策略的单模式匹配算法 总被引:2,自引:0,他引:2
结合后缀有限自动机和正向有限自动机的优点,提出了两个单模式匹配算法.算法中,无论是后缀自动机还是正向有限自动机,只要扫描到的模式前缀长度R>0或者超过模式长度的1/2时,使用正向有限自动机继续向右进行扫描;否则都滑动m-R个字符,使用后缀自动机反向扫描模式串的前缀.两个算法的最差、最好时间复杂度分别为O(n)和O(n/m).结果表明,在短模式的情况下,两个算法的平均时间复杂度均好于RF和LDM,在小字符集长模式或大字符集短模式的情况下它们的平均性能好于BM. 相似文献
16.
江志松 《华东理工大学学报(自然科学版)》2006,32(4):492-496
研究了122号初等元胞自动机的演化语言,证明了其宽度为1的演化语言是正规的,宽度大于1的演化语言不是正规的。结果表明:仅用有限自动机是无法接受由122号初等元胞自动机产生的演化语言。 相似文献
17.
李捷 《五邑大学学报(自然科学版)》2011,(4):50-56
针对期权定价难于模拟基础资产价格波动随机性的问题,设计了基于元胞自动机的期权定价模型.该模型将市场参与者看作一个个的元胞,使用元胞规则来模拟金融市场中交易者之间的交互行为。从而在总体上模拟出基础资产价格的变化.比较了模型产出的数据和Black-Scholes模型的计算结果,检验了模型产出数据的正态性,发现基于元胞自动机的期权定价模型不仅具有可行性,而且比Black-Scholes模型更有效. 相似文献
18.
通过定义164号元胞自动机的基本粒子,找到了粒子的逆演化规律,从而完全确定了其极限语言,并证明了164号元胞自动机的极限语言是正规的。结果表明:用有限自动机就可以接收该极限语言。 相似文献
19.
在图像边界标定算法的基础上,通过化简自动机的状态迁移映射,减少了自动机在提取边界过程中的运算步骤和存储空间,提高了自动机效率. 相似文献