有穷自动机

DFA

在这里插入图片描述

在这里插入图片描述

DFA的表示方法

  1. 五元组
  2. 状态转移表
  3. 状态转移图

示例:

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

DFA 的设计举例

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

非确定有穷自动机

在这里插入图片描述

非确定有穷自动机与确定的有穷自动机的主要差别在于状态转移函数,DFA转到一个状态,NFA转到一个状态集合

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

NFA示例

在这里插入图片描述

例8答案:

[外链图片转存失败(img-ikV0jjA5-1568786198995)(C:UsersNormanDesktopFILEM2 工作TYPORA图片l.jpg)]

在这里插入图片描述

DFA 和 NFA

在这里插入图片描述

将NFA 转为DFA: 子集构造法

1560734437104

上述方法的理解:

  1. 状态是以集合的方式来表示,如一个状态可以是{q,r,s}
  2. 结束状态集合可以有多个,只要每个状态集合中包含NFA的结束状态就可以
  3. 状态转移结果是一个集合

非确定性没能增加有穷自动机识别语言的能力

先将NFA变成DFA的状态转移表,再变成状态转移函数

在这里插入图片描述

在这里插入图片描述

有空转移的NFA

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

状态的闭包

在这里插入图片描述

在这里插入图片描述
状态集的闭包即状态集中所有元素经空转移能到达的状态

在这里插入图片描述

在这里插入图片描述

此处的状态转移函数只是为了空转移稍微改变了形式,本质没有变

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

将带空转移的NFA变成DFA

在这里插入图片描述

即将一个状态的闭包中的所有状态合并

可接受状态很可能会增加

同样是先构造状态转移表(不需要写空转移),再构造状态转移图

在这里插入图片描述

在这里插入图片描述

自动机的最小化

在这里插入图片描述

等价性:只要你可以通过串w到达终点, 我也可以

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/lee3258/p/11997777.html