一、确定性有穷自动机组成

DFA , 全称为 Deterministic Finite Automaton , 确定性有穷自动机 ;

确定性 有穷自动机 组成 : 由以下的 $5$ 部分组成 , 放入集合中展示 $\{Q,\Sigma ,,\delta ,q_0,F\}$ ;

① $Q$ 状态集 : 有限个状态 ;

② $\Sigma$ 字母表 : 有限个字符集 , 长度有限的字符串 ;

③ $\delta$ 转移函数 : $\delta$ 称为转移函数 ; 基于当前的 自动机 的某个状态 , 将字符集 输入到自动机中 , 该自动机转换成另一个状态 , 这个转换就是通过 $\delta$ 转换函数进行的 , 使用公式描述 $Q\times \Sigma \to Q$ ;

④ $q_0$ 起始状态 : 是自动机的开始状态 ;

⑤ $F$ 接受状态集 : $F$ 是 可接受状态 , 是 $Q$ 的子集 , 记做 $F\subseteq Q$ , 与 $F$ 可接受状态相对的是不可接受状态 ;

二、确定性有穷自动机计算过程

1 . 自动机示例 : 上图是上一篇博客的自动机示例 , 自动机开始执行后 , 将 字符串 “$0101$” 输入到自动机中 , 从 Start 出发 , 根据当前的自动机状态 , 结合当前处理的输入字符 , 改变成另外一个自动机状态 , 所有字符处理完毕后 , 查看当前自动机状态是否是可接受状态 ;

2 . 自动机运行过程 : 详细的计算过程 , 参考上一篇博客 : 【计算理论】自动机 示例 ( 自动机示例 | 自动机表示方式 | 自动机计算流程简介 )

3 . 自动机定义由来 : 将 $\{Q,\Sigma ,,\delta ,q_0,F\}$ 五个组件代入上述过程 , 就可以得到自动机定义 ;

三、确定性有穷自动机定义

确定性又穷自动机定义

1 . 有以下已知条件 :

① 有穷自动机 : $M$ ;

② 输入信息 : 接收 $w$ 字符串作为输入 , $w$ 字符串可以写成 $\{w_1,w_2,w_3,\cdots w_m\}$ 等 $m$ 个字符 ; 其中 每个字符都属于有限字符集 $\Sigma$ 中的字符 , 这些字符有重复的 , 这是输入序列 , 下面是状态序列 ; $m$ 是总共计算的次数 ;

③ 状态序列 : 自动机 $M$ 有以下 $m+1$ 个状态序列 , $\{r_0,r_1,r_2,\cdots ,r_m\}$ , 这个序列中的状态有很多重复的 , 这是自动机的执行序列 , 途径的状态 , 所有的状态都属于 $Q$ ; 这是 自动机 $M$ 计算过程中的 状态序列 , 上面的输入信息时每个状态序列对应的输入序列 ; $m$ 是总共计算的次数 ;

2 . 上述条件满足如下计算 :

① 自动机起始状态 : $r_0=q_0$ , 自动机 $M$ 开始时 , 是 $q_0$ 起始状态 , 相当于上图中的 Start 状态 ; 这也是为什么状态序列比输入信息序列多一个原因 , 状态序列开始必须有一个状态 , 之后每接受一个参数字符 , 就更新一个新的状态 , 之后就状态与输入字符就是一一对应的 ; 最后状态序列 比 字符序列多一个 ;

② 自动机计算 : 对于 $1=0,1,\cdots ,m-1$ , 有 $\delta (r_i,w_{i+1})=r_{i+1}$ , 意思就是 当前是自动机的一个状态 $r_i$ , 输入一个 $w_{i+1}$ 字符后 , 变成了 $r_{i+1}$ 状态 ;

③ 最终状态可接受 : 最终的 $r_m$ 状态必须是可接受状态 , $r_m\in F$ ;

3 . 自动机组件 :

① $Q$ 状态集 : 自动机的有限个状态 , 其中有可接受状态 ( 双圈 ) , 不可接收状态 ( 单圈 ) ;

② $\Sigma$ 字母表 : 有限个字符集 , 如 $\{0,1\}$ , 但其输入可以是 $0101$ , 也可以是 $00111$ 等字符 ;

③ $\delta$ 转移函数 : $\delta$ 称为转换函数 ; 基于当前的 自动机 的某个状态 , 将字符集 输入到自动机中 , 该自动机转换成另一个状态 , 这个转换就是通过 $\delta$ 转换函数进行的 , 使用公式描述 $Q\times \Sigma \to Q$ ;

④ $q_0$ 起始状态 : 是开始状态 ;

⑤ $F$ 接受状态集 : $F$ 是 可接受状态 , 是 $Q$ 的子集 , 记做 $F\subseteq Q$ , 与 $F$ 可接受状态相对的是不可接受状态 ;

四、自动机 语言 与 等价

1 . 自动机语言 : 确定性有穷自动机 $M$ , 将自动机 $M$ 所接受的所有的字符串放在一个集合 $A$ 中 , 该集合 $A$ 称为自动机 $M$ 的语言 , 自动机 $M$ 认识 ( 接受 ) $A$ 语言 , 记作 $L(M)=A$ ;

2 . 自动机等价 : 如果两个自动机认识相同的语言 , 那么称这两个自动机是等价的 ;

五、自动机语言 示例

1 . 自动机描述 :

自动机有 $5$ 个状态 ;

$S$ 是开始状态 ;

$q_1,r_1$ 是可接受状态 ;

$q_2,r_2$ 是不可接受状态 ;

自动机语言是 $\{a,b\}$ 字符集 ;

下面开始分析上面 $5$ 状态自动机的语言 ;

2 . 自动机 左侧分支分析 :

① 执行流程 : 开始时 , 自动机是 $S$ 起始状态 , 当输入 $a$ 时 , 自动机状态变成 $q_1$ , 此后不管多少次输入 $a$ , 一直处于 $q_1$ 状态 , 如果输入 $b$ , 那么就会转为 $q_2$ 状态 , 如果一直输入 $b$ , 自动机一直处于该非接受状态 $q_2$ , 如果输入 $a$ , 又回到接受状态 $q_1$ ;

② 左侧分支分析总结 : 左侧分支 , 主要接受 以 $a$ 开头 , 以 $a$ 结尾的字符串 , 最后才能进入接受状态 ;

3 . 自动机 右侧分支分析 :

① 执行流程 : 开始时 , 自动机是 $S$ 起始状态 , 当输入 $b$ 时 , 自动机状态变成 $r_1$ , 此后不管多少次输入 $b$ , 一直处于 $r_1$ 状态 , 如果此时输入 $a$ , 那么就会转为 $r_2$ 状态 , 此时如果一直输入 $a$ , 自动机一直处于该非接受状态 $r_2$ , 如果输入 $b$ , 又回到接受状态 $r_1$ ;

② 右侧分支分析总结 : 右侧分支 , 主要接受 以 $b$ 开头 , 以 $b$ 结尾的字符串 , 最后才能进入接受状态 ;

4 . 自动机 总体分析 : 自动机 $M$ 接受相同开头 和 相同结尾的 字符串 ;

5 . 接受状态 与 非接受状态 : 只在计算结束以后才开始起作用 ;

① 计算过程 : 在计算过程中 , 这两个状态没有区别 , 可以任意转换 ;

② 最终状态 : 自动机的 最终的状态 , 必须判定失接受状态 还是 非接受状态 , 如果是非接受状态 , 说明输入不对 , 自动机拒绝该输入 ;

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/106043491