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

2023-03-27 20:06:31 浏览数 (1)

文章目录

  • 一、确定性有穷自动机组成
  • 二、确定性有穷自动机计算过程
  • 三、确定性有穷自动机定义
  • 四、自动机 语言 与 等价
  • 五、自动机语言 示例

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

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

确定性 有穷自动机 组成 : 由以下的

5

部分组成 , 放入集合中展示

{ quad Q , quad Sigma , quad , delta quad , q_0 , quad F quad }

;

①

Q

状态集 : 有限个状态 ;

②

Sigma

字母表 : 有限个字符集 , 长度有限的字符串 ;

③

delta

转移函数 :

delta

称为转移函数 ; 基于当前的 自动机 的某个状态 , 将字符集 输入到自动机中 , 该自动机转换成另一个状态 , 这个转换就是通过

delta

转换函数进行的 , 使用公式描述

Q times Sigma to Q

;

④

q_0

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

⑤

F

接受状态集 :

F

是 可接受状态 , 是

Q

的子集 , 记做

F subseteq Q

, 与

F

可接受状态相对的是不可接受状态 ;

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

1 . 自动机示例 : 上图是上一篇博客的自动机示例 , 自动机开始执行后 , 将 字符串 “

0101

” 输入到自动机中 , 从 Start 出发 , 根据当前的自动机状态 , 结合当前处理的输入字符 , 改变成另外一个自动机状态 , 所有字符处理完毕后 , 查看当前自动机状态是否是可接受状态 ;

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

3 . 自动机定义由来 : 将

{ quad Q , quad Sigma , quad , delta quad , q_0 , quad F quad }

五个组件代入上述过程 , 就可以得到自动机定义 ;

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

确定性又穷自动机定义

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 . 接受状态 与 非接受状态 : 只在计算结束以后才开始起作用 ;

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

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

博客 函数 集合 字符串

0 人点赞