微笑如一
首页 网络收藏 分解查字

相关: 相似查询
浏览:318
内容:

自动机是一种理想化的“机器”,它只是抽象分析问题的理论工具,并不具有实际的物质形态。
自动机是科学定义的演算机器,用来表达某种不需要人力干涉的机械性演算过程。

【有限自动机】(finite automata)FA
确定性有限自动机(definite automata, DFA)
不确定性有限自动机(non-definite automata, NFA)

有限自动机【五元组】:M=(Σ,Q,δ,q0,F)
Σ是输入符号的有穷集合;
Q是状态的有限集合;
q0∈Q是初始状态;
F是终止状态集合,F⊆Q;
δ是Q与Σ的直积Q×Σ到Q(下一个状态)的映射,它支配着有限状态控制的行为,有时也称为【状态转移函数】。

【DFA和NFA的区别】:
在NFA中δ(q, a)是一个状态集合,即有多个状态转移。
在DFA中δ(q, a)是一个状态。即只有一个状态转移。
(“确定”意味着对于一个输入字符,只有唯一的可能状态)

有穷自动机(finite state automata)是一个识别器,它对每个输入的字符做识别和判断,以确定其能到达的最终状态或状态集和路径。

如果一个字符串从一个DFA的初始状态出发,能在某一个终止状态结束,那这个字符串就被这个DFA所接受。
所有的这种字符串的集合就是这个自动机的语言(language)。

有穷指的是自动机的状态个数是有限的。

有限状态自动机(FSM "finite state machine" 或者FSA "finite state automaton" )是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。
有限状态自动机拥有有限数量的状态,每个状态可以迁移到零个或多个状态,输入字符串决定执行哪个状态的迁移。有限状态自动机可以表示为一个有向图。
有限状态自动机是自动机理论的研究对象。 

有限状态机,(英语:Finite-state machine, FSM),又称有限状态自动机,简称状态机,是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。

参考:
自动机理论
https://www.jianshu.com/p/f1e279a47b04
有穷自动机DFA&NFA (学习笔记)
https://zhuanlan.zhihu.com/p/30009083
有穷自动机(有穷状态自动机)简介
https://kb.cnblogs.com/page/104928/
自动机
https://baike.baidu.com/item/自动机

联系: web@xiaoruyi.cn