- 形式语言自动机课程笔记
- 学到编译原理的时候用到了相关概念,复习自动机正好把以前的笔记整理一下也贴上来
文章目录
- 〇、我的理解
- 一、确定型有穷自动机(DFA)
- (1)基本定义
- (2)扩充定义
- (3)DFA接受的语言
- 二、非确定型有穷自动机(NFA)
- (1)基本定义
- (2)扩充定义
- (3)NFA接受的语言
- 三、具有ε转移的有穷自动机(ε-NFA)
- (1)基本定义
- (2)扩充定义
- (3)ε-NFA接受的语言:
- 四、小结
〇、我的理解
说一说我对自动机的个人理解,仅供参考
- 自动机是描述多状态系统的一种方法。比如指针式钟表就是一种多状态系统,它有12x60x60个状态,秒针没走一格,就切换到下一个相邻的状态。 同时,自动机是表示语言的另一种形式,具体见下面的分析
- 自动机的组成
- 既然是描述的多状态系统,那么自然有很多状态
- 状态之间的存在转移,这种转移:
- 是有规则的:比如时钟只能就只能在相邻时刻,从过去向将来进行切换。比如从12:00:00切换到12:00:01,不能出现从从12:00:00切换到13:00:00之类的情况
- 是输入驱动的:系统只有获得输入后发生状态转移,如果没有输入,就不会切换状态。还是以时钟为例,驱动转换发生的是系统获得输入“时间流逝1秒”(事实上某些系统也可能有自发的转移发生,这时要把输入定义为
空ε
) - 转换的三要素是 “转移前状态”、“输入”、“转移后状态”,有这三点就能清楚地描述一个转移
- 多状态系统一定有且只有一个初态,至少有一个终态。规定自动机未获得任何输入时的状态是初态(状态转换从初态开始);终态是人为指定的,即使达到某个终态了,也可以继续接受输入并转换到自己、其他终态或非终态
- 对于某些状态,无论输入什么,都不能驱动其最终转换到终态(经过任意多次状态转换都不行),这种状态称它为死状态。
- 对多状态系统进行抽象:
- 有若干状态
- 存在若干输入
- 状态间存在由输入驱动的转移
- 有一个特殊的初始态
- 有若干特殊的终结态
- 和语言的联系:除了之前介绍的文法外,自动机是表示语言的另一种形式。
- 语言说白了就是一些字符串的集合,只要设计一个"系统",可以把某些字符串从世界上无穷多的字符串中提取出来,就可以说这个"系统"能表示语言。
- 我们把字符串拆开为一个个字符,每个字符作为一个输入。自动机从初始态开始,受到每一个字符的输入不停进行状态转移,当字符串全部输入后,如果自动机处于某个终结状态,我们就说自动机接受了这个字符串。所有自动机接受的字符串的集合称为这个自动机描述的语言
- 自动机的分类:基于状态转移规则形式上的不同进行分类
一、确定型有穷自动机(DFA)
(1)基本定义
-
确定有穷自动机DFA
:是一个五元组:,其中
- 是有穷状态集;
- 是有穷的输入字母表
- 是转移函数,它进行全映射
- ,是初始状态;
- ,是终结状态集。(终止状态,接受状态)
- DFA的表示方法
- 状态转换函数
- 状态转移矩阵
- 状态转移图
1. 是一张有限方向图,结点代表状态,用圆圈表示。状态之间用箭弧连结。
2. 箭弧上的标记(字符或正规式)代表在射出结点(即箭符始结点)状态下可能出现的输入字符或字符类。
3. 初态,用双线箭头指示,表示分析的开始
4. 终态,用双圈表示,表示分析的结束
5. 一张状态转换图只包含有限个状态(即有限个结点),其中含有一个初态和若干个终态(至少一个)。
6. 一个状态转换图可用于识别(或接受)一定的字符串
- 注意:
- DFA的转移函数是全映射,也就是说:对于n个字母表元素,如果不省略死状态,DFA每个状态一定有n个转移(出箭头)
(2)扩充定义
-
扩充转移函数
:对于DFA ,它的扩充转移函数 是从的映射,其具体定义如下:
- 简单说就是把转移函数的第二个变元扩充为字符串,表示从状态q读过串后转移到状态q’,是的特例
- 一般DFA的都指扩充定义
(3)DFA接受的语言
给出DFA
-
DFA接受的字符串
:若(即串x使起始状态转移到终结状态集),则称字符串x被M接受 -
DFA接受的语言
:被M接受的全部字符串构成的集合,称为被有穷自动机M接受的语言,并记为L(M)={ x ∣δ(q0,x)∈F,x∈∑*}
- 从状态转移图角度看:状态转移图上,任何一条从某一初态结点到某一终态结点的通路,其上所有弧的标记字依序连接成的字符串(忽略那些标记为ε的弧)等于α,则称α可为DFA M所识别(读出或接受),α也可能是空串ε
二、非确定型有穷自动机(NFA)
(1)基本定义
-
非确定有穷自动机NFA
:一个五元组
- 其中与DFA含意相同,
- 上的映射。
注意这里状态转移函数右边是集合了,应写成集合形式{…}
- 说明:
- NFA的运行过程中某个时刻是会同时处于多个状态中,只要输入串x结束时NFA所处的多个状态中至少有一个是接受状态,就判断NFA接受x
- 这相比DFA增加了不确定性,加强了其表达能力。可以理解成描述同一个多状态系统时,NFA比DFA形式更简便
- 注意:
- n个字母表元素,NFA每个状态不一定有n个转移(出箭头),有些没定义,δ为Ø
(2)扩充定义
-
扩充转移函数
:扩展为:的映射,具体定义如下
- 可以看到这里变成了从集合到集合的映射,输入也从一个字符变成了字母表闭包(字符或字符串)
- 这样理解:假设初始状态集是,从第一个元素开始读串x,读过第一个符号转移到若干状态,构成一个状态集,再对状态集中的n个状态,分别读取下一个符号,得到的n个状态并起来得到。再对其中每一个状态读取下一个符号直到读完得到,则,依次处理状态集中所有初始状态,得到,全部取并即可
- 一般NFA的都指扩充定义
(3)NFA接受的语言
给出NFA
-
NFA接受的字符串
:若,则称字符串x被M接受 -
被NFA接受的语言L(M)
:被NFA M接受的全体字符串称为M接受的语言
三、具有ε转移的有穷自动机(ε-NFA)
(1)基本定义
-
具有ε转移的有穷自动机(ε-NFA)
:是一个五元组
- 其中Q,∑,q0,F的含义与一般的DFA或 NFA相同
- δ是映射。
- 说明:
- 和普通NFA相比,可能出现自发转移ε,即没有输入也有可能发生转移动作
- 这相比普通NFA增加了不确定性,加强了其表达能力。
- 注意:
- n个字母表元素,NFA每个状态不一定有n个转移(出箭头),有些没定义,δ为Ø
(2)扩充定义
-
ε-CLOSURE(q)
:有ε-NFA,对于状态q,它的ε-CLOSURE(q)是:
- 形式化定义:
- q在ε-CLOSURE(q)中;
- 若p在ε-CLOSURE(q)中,则δ(p,ε)也都在ε-CLOSURE(q)中;
- 重复2,直到ε-CLOSURE(q)中状态不再增加为止。
- 进一步地,对于状态集P的ε-CLOSURE( P),我们规定:ε-CLOSURE( P) = ∪ε-CLOSURE(q),也就是所有元素的ε-CLOSURE并起来
- 从转移图上看,就是从状态q出发,沿着标有ε的有向边所能达到的一切状态所构成的集合(包括状态q本身)
-
扩充转移函数
:扩展为映射 ,定义如下:
- (q,wa)=ε-CLOSURE( P), P = (r,a),r∈(q,w)(q∈Q, a∈∑, w∈∑*)
- 这样理解:假设初始状态集是,从第一个元素开始读串x,先扩展(读ε),然后对结果集合中每一个读第一个字符计算转移状态集,然后全部并(得),对所得集合中每个做ε扩展,再合并(至此得到读一个字符的结果),对结果集合中每一个读第二个字符计算转移状态集,然后求并/每个扩展/求并。重复“每个元素读入一个/求并/扩展/求并”,直到读完
- 对于ε-NFA,和`必须要区分
(3)ε-NFA接受的语言:
给出ε-NFA ,它接受的语言定义为:
-
被ε-NFA接受的语言L(M)
:
四、小结
- DFA、NFA、ε-NFA表达能力依次提高,因为引入的不确定性越来越高。
- 三者的接受能力没有变化,换句话说这三者是等价的