一文搞定有穷状态自动机(FA) |
您所在的位置:网站首页 › 理解空集的概念是什么 › 一文搞定有穷状态自动机(FA) |
有穷状态自动机(Finite Automata, FA)分为确定的和不确定的,简称为DFA和NFA。 确定有穷自动机(DFA)形式定义:
形式定义: DFA与NFA的区别在于,NFA的状态转换过程中可以有空串,如下图即为NFA。
所以NFA的不确定表现我们可以概括为: 多值映射带空转移因此在很多时候,我们都需要将NFA转换为DFA。 NFA转换为DFA理论准备: 定义1的意思便是,在当前状态下,我们首先将当前状态以及经过空串能够到达的状态放到一起组成一个闭包。 定义2的意思便是,将该闭包中的每个状态,都加上一个确定的输入,如外界输入一个a,从而进入到新的状态,再将这些新的状态以及这些新的状态加上空串能够到达的状态放到一起组成一个新的闭包。 对于正规式 : 则经过确定化可以得到如下表格: 经过确定化处理之后,我们可以发现,已经没有空串了,每个状态都是确定的。 然后对表格进行重新编号:
等价状态:若分别从状态 s 和 t 出发而停于终态能读出同一个串α,则称s, t 为等价状态;反之则称为可区别状态。 其中,终态与非终态一定是可区别的。
则首先状态集S={0, 1, 2, 3, 4, 5, 6}可以分为S1={0, 1, 2}和S2={3, 4, 5, 6} 那么对于S1,0,1,2是可区别的吗? 由于0状态下输入a进入状态1,输入b进入状态2;1状态输入a进入终态3,输入b进入状态2;2状态输入a进入状态1,输入b进入终态4。 可以发现,0,1,2状态进入终态的路径集合都不相同,因此相互之间都是可区别的。 对于S2,由于3,4,5,6状态输入a,b都能够直接进入到终态,即进入终态的路径集合都是一样的,因此是等价状态。 综上所述,S最终可以被分割为(0)S11={0},(1)S12={1},(2)S13={2}以及(3)S2={3, 4, 5, 6},DFA简化为: |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |