【计算理论】确定性有穷自动机 ( 自动机组成 | 自动机语言 | 自动机等价 )

I . 确定性有穷自动机组成

---

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

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

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

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

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

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

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

II . 确定性有穷自动机计算过程

---

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

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

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

III . 确定性有穷自动机定义

---

确定性又穷自动机定义

1 . 有以下已知条件 :

① 有穷自动机 : $M$M ;

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

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

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

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

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

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

3 . 自动机组件 :

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

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

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

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

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

IV . 自动机 语言 与 等价

---

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

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

V . 自动机语言 示例

---

1 . 自动机描述 :

自动机有 $5$5 个状态 ;

$S$S 是开始状态 ;

$q_1 , r_1$q1​,r1​ 是可接受状态 ;

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

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

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

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

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

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

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

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

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

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

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

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

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