不确定有穷自动机 NFA 定义为一个五元组
如下:
比如说下面的NFA:
其状态转移图如下:
∑*上的符号串t被NFA M接受也可以这样理解<o:p></o:p>
对于Σ﹡中的任何一个串t,若存在一条从某一初态节点到某一终态节点的道路,且这条道路上所有弧的标记依序连接成的串(不理采那些标记为ε的弧)等于t,则称t可为NFA M所识别(读出或接受)。若M的某些节点既是初态节点又是终态节点,或者存在一条从某个初态节点到某个终态节点的道路,其上所有弧的标记均为ε,那么空字可为M所接受。<o:p></o:p>
再来看一下隐马尔可夫模型 HMM的相关定义
<p:colorscheme colors="#0066ff,#ffffff,#000000,#ffff00,#00cccc,#ff33cc,#ff4568,#ccecff"></p:colorscheme>
n用模型五元组 =( N, M, π ,A,B)用来描述HMM,或简写为 =(π ,A,B)
<p:colorscheme colors="#0066ff,#ffffff,#000000,#ffff00,#00cccc,#ff33cc,#ff4568,#ccecff"></p:colorscheme>
参数
|
含义
|
N
|
状态数目
|
M
|
每个状态可能的观察值数目
|
A
|
与时间无关的状态转移概率矩阵
|
B
|
给定状态下,观察值概率分布
|
π
|
初始状态空间的概率分布
|
NFA 由一个状态可能会转移到不同的状态;
HMM 由一个状态可能会转移到不同的状态;
NFA 转移到不同的状态由输入字母确定
HMM 转移到不同的状态由状态转移概率矩阵决定
NFA 中的输入字母与 HMM 的观察值是非常类似的
对于一个给定的字符串
NFA 给出的判断是 接收该串(1)或者拒绝该串(0)
HMM 给出的判断是 该观测值序列(串)出现的概率(01之间)
针对同一个输入
NFA状态转移不确定
HMM状态转移概率是确定的
NFA 状态转移函数通过固定规则指定
HMM 状态转移概率通过统计学习获得
最大的差别就是:
NFA是规则的
而HMM是统计的
暂时就想到这么多了
想到了再来完善
分享到:
相关推荐
输入:非确定有穷状态自动机NFA 输出:确定化的有穷状态自动机DFA
不确定有穷自动机转化为确定的有穷自动机的C++源代码
为NFA.java 文件中的NFA 类实现成员函数boolean recognizeString(int move[][][], int accept_state[], String word)
基于NFA(不确定有穷自动机)与自底向上语法分析构造的正则表达式解析器
有穷自动机转化为正规式,输入一个有穷自动机,把它转化为正规式,最好是NFA,DFA也可以。
针对Robocup自主机器人比赛中,机器人进攻和防守状态、动作转换延迟问题,采用一种基于有穷自动机模型的自然语言状态转换方法,把机器人、环境等自然语言信息抽象成形式化的符号和状态,并转化为有穷自动机输入符号....
正规式到有穷自动机源代码
1. 正规式 2. 有穷自动机正规式匹配 3. 有穷自动机工作原理 模拟NFA或者模拟DFA
编译原理实验(确定有穷状态自动机) 输入正则文法 输出状态集合 字母表 开始状态终止状态 以及识别句子
识别浮点数的有穷自动机识别浮点数的有穷自动机识别浮点数的有穷自动机识别浮点数的有穷自动机
从正则表达式到有穷自动机实例 从正则表达式到有穷自动机实例
有穷自动机,自动机最小化,串匹配,压缩,性能
简单的模拟dfa实验代码,基于表驱动的dfa确定的有穷自动机
wc有穷自动机.doc
期末课程设计必备 自己捣鼓的 其实没有什么内容 下吧 下吧
马尔可夫模型的概念是一个离散时域有限状态自动机,隐马尔可夫模型HMM是指这一马尔可夫模型的内部状态外界不可见,外界只能看到各个时刻的输出值。对语音识别系统,输出值通常就是从各个帧计算而得的声学特征。用HMM...
智能优化算法、神经网络预测、信号处理、元胞自动机、图像处理、路径规划、无人机等多种领域的Matlab仿真代码
汉字有穷自动机研究汉字有穷自动机研究汉字有穷自动机研究
自动机DFA与NFA转化和最下化的代码实现软件,相信对大家研究自动机有好处。
有穷自动机等价转化中的一种重要工具, 以有穷自动机为工具,对网络原始数据进行监测,发现有价值舆情信息。...尽量不让敏感词汇出现在类似于论坛之类的公共交流平台上,让有穷自动机在舆情监测中起到重要的作用。