首页 > 其他分享 >形式语言自动机(3)—— 三种有穷自动机

形式语言自动机(3)—— 三种有穷自动机

时间:2022-11-22 10:38:00浏览次数:60  
标签:状态 形式语言 NFA 有穷 自动机 DFA 转移 定义


  • 形式语言自动机课程笔记
  • 学到编译原理的时候用到了相关概念,复习自动机正好把以前的笔记整理一下也贴上来

文章目录

  • ​​〇、我的理解​​
  • ​​一、确定型有穷自动机(DFA)​​
  • ​​(1)基本定义​​
  • ​​(2)扩充定义​​
  • ​​(3)DFA接受的语言​​
  • ​​二、非确定型有穷自动机(NFA)​​
  • ​​(1)基本定义​​
  • ​​(2)扩充定义​​
  • ​​(3)NFA接受的语言​​
  • ​​三、具有ε转移的有穷自动机(ε-NFA)​​
  • ​​(1)基本定义​​
  • ​​(2)扩充定义​​
  • ​​(3)ε-NFA接受的语言:​​
  • ​​四、小结​​

〇、我的理解

说一说我对自动机的个人理解,仅供参考

  1. 自动机是描述多状态系统的一种方法。比如指针式钟表就是一种多状态系统,它有12x60x60个状态,秒针没走一格,就切换到下一个相邻的状态。 同时,自动机是表示语言的另一种形式,具体见下面的分析
  2. 自动机的组成
  • 既然是描述的多状态系统,那么自然有很多状态
  • 状态之间的存在转移,这种转移:
  1. 有规则的:比如时钟只能就只能在相邻时刻,从过去向将来进行切换。比如从12:00:00切换到12:00:01,不能出现从从12:00:00切换到13:00:00之类的情况
  2. 输入驱动的:系统只有获得输入后发生状态转移,如果没有输入,就不会切换状态。还是以时钟为例,驱动转换发生的是系统获得输入“时间流逝1秒”(事实上某些系统也可能有自发的转移发生,这时要把输入定义为空ε​)
  3. 转换的三要素是 “转移前状态”、“输入”、“转移后状态”,有这三点就能清楚地描述一个转移
  4. 多状态系统一定有且只有一个初态至少有一个终态。规定自动机未获得任何输入时的状态是初态(状态转换从初态开始);终态是人为指定的,即使达到某个终态了,也可以继续接受输入并转换到自己、其他终态或非终态
  5. 对于某些状态,无论输入什么,都不能驱动其最终转换到终态(经过任意多次状态转换都不行),这种状态称它为死状态
  1. 对多状态系统进行抽象:
  1. 有若干状态
  2. 存在若干输入
  3. 状态间存在由输入驱动的转移
  4. 有一个特殊的初始态
  5. 有若干特殊的终结态
  1. 和语言的联系:除了之前介绍的文法外,自动机是表示语言的另一种形式
  1. 语言说白了就是一些字符串的集合,只要设计一个"系统",可以把某些字符串从世界上无穷多的字符串中提取出来,就可以说这个"系统"能表示语言。
  2. 我们把字符串拆开为一个个字符,每个字符作为一个输入。自动机从初始态开始,受到每一个字符的输入不停进行状态转移,当字符串全部输入后,如果自动机处于某个终结状态,我们就说自动机接受了这个字符串。所有自动机接受的字符串的集合称为这个自动机描述的语言
  1. 自动机的分类:基于状态转移规则形式上的不同进行分类

一、确定型有穷自动机(DFA)

(1)基本定义

  • ​确定有穷自动机DFA​​​ :是一个五元组:形式语言自动机(3)—— 三种有穷自动机_字符串,其中
  1. 形式语言自动机(3)—— 三种有穷自动机_有穷自动机_02有穷状态集
  2. 形式语言自动机(3)—— 三种有穷自动机_状态转移_03是有穷的输入字母表
  3. 形式语言自动机(3)—— 三种有穷自动机_状态转移_04转移函数,它进行全映射形式语言自动机(3)—— 三种有穷自动机_字符串_05
  4. 形式语言自动机(3)—— 三种有穷自动机_有穷自动机_06,是初始状态
  5. 形式语言自动机(3)—— 三种有穷自动机_字符串_07,是终结状态集。(终止状态,接受状态)
  • DFA的表示方法
  1. 状态转换函数
  2. 状态转移矩阵
  3. 状态转移图

    1. 是一张有限方向图,结点代表状态,用圆圈表示。状态之间用箭弧连结。
    2. 箭弧上的标记(字符或正规式)代表在射出结点(即箭符始结点)状态下可能出现的输入字符或字符类。
    3. 初态,用双线箭头指示,表示分析的开始
    4. 终态,用双圈表示,表示分析的结束
    5. 一张状态转换图只包含有限个状态(即有限个结点),其中含有一个初态和若干个终态(至少一个)。
    6. 一个状态转换图可用于识别(或接受)一定的字符串
  • 注意:
  1. DFA的转移函数是全映射,也就是说:对于n个字母表元素,如果不省略死状态,DFA每个状态一定有n个转移(出箭头)

(2)扩充定义

  • ​扩充转移函数​形式语言自动机(3)—— 三种有穷自动机_状态转移_08:对于DFA 形式语言自动机(3)—— 三种有穷自动机_有穷自动机_09,它的扩充转移函数 是从形式语言自动机(3)—— 三种有穷自动机_状态转移_10的映射,其具体定义如下:
  1. 形式语言自动机(3)—— 三种有穷自动机_有穷自动机_11
  2. 形式语言自动机(3)—— 三种有穷自动机_字符串_12
  • 简单说就是把转移函数的第二个变元扩充为字符串,表示从状态q读过串后转移到状态q’形式语言自动机(3)—— 三种有穷自动机_字符串_13形式语言自动机(3)—— 三种有穷自动机_状态转移_08的特例
  • 一般DFA的形式语言自动机(3)—— 三种有穷自动机_字符串_13都指扩充定义

(3)DFA接受的语言

给出DFA 形式语言自动机(3)—— 三种有穷自动机_字符串_16

  • ​DFA接受的字符串​​​:若形式语言自动机(3)—— 三种有穷自动机_有穷自动机_17即串x使起始状态转移到终结状态集),则称字符串x被M接受
  • ​DFA接受的语言​​:被M接受的全部字符串构成的集合,称为被有穷自动机M接受的语言,并记为​​L(M)={ x ∣δ(q0,x)∈F,x∈∑*}​
  • 从状态转移图角度看:状态转移图上,任何一条从某一初态结点到某一终态结点的通路,其上所有弧的标记字依序连接成的字符串(忽略那些标记为ε的弧)等于α,则称α可为DFA M所识别(读出或接受),α也可能是空串ε

二、非确定型有穷自动机(NFA)

(1)基本定义

  • ​非确定有穷自动机NFA​​​:一个五元组形式语言自动机(3)—— 三种有穷自动机_状态转移_18
  1. 其中形式语言自动机(3)—— 三种有穷自动机_字符串_19与DFA含意相同,
  2. 形式语言自动机(3)—— 三种有穷自动机_字符串_20上的映射。

注意这里状态转移函数右边是集合了,应写成集合形式{…}

  • 说明:
  1. NFA的运行过程中某个时刻是会同时处于多个状态中,只要输入串x结束时NFA所处的多个状态中至少有一个是接受状态,就判断NFA接受x
  2. 这相比DFA增加了不确定性,加强了其表达能力。可以理解成描述同一个多状态系统时,NFA比DFA形式更简便
  • 注意:
  1. n个字母表元素,NFA每个状态不一定有n个转移(出箭头),有些没定义,δ为Ø

(2)扩充定义

  • ​扩充转移函数​形式语言自动机(3)—— 三种有穷自动机_状态转移_08:扩展为:形式语言自动机(3)—— 三种有穷自动机_有穷自动机_22的映射,具体定义如下
  1. 形式语言自动机(3)—— 三种有穷自动机_有穷自动机_23
  2. 形式语言自动机(3)—— 三种有穷自动机_字符串_24
  • 可以看到这里变成了从集合到集合的映射,输入也从一个字符变成了字母表闭包(字符或字符串)
  • 这样理解:假设初始状态集是形式语言自动机(3)—— 三种有穷自动机_状态转移_25,从第一个元素形式语言自动机(3)—— 三种有穷自动机_状态转移_26开始读串x,读过第一个符号转移到若干状态,构成一个状态集形式语言自动机(3)—— 三种有穷自动机_有穷自动机_27,再对状态集形式语言自动机(3)—— 三种有穷自动机_有穷自动机_27中的n个状态,分别读取下一个符号,得到的n个状态并起来得到形式语言自动机(3)—— 三种有穷自动机_状态转移_29。再对其中每一个状态读取下一个符号直到读完得到形式语言自动机(3)—— 三种有穷自动机_字符串_30,则形式语言自动机(3)—— 三种有穷自动机_字符串_31,依次处理状态集形式语言自动机(3)—— 三种有穷自动机_状态转移_25中所有初始状态,得到形式语言自动机(3)—— 三种有穷自动机_有穷自动机_33,全部取并即可
  • 一般NFA的形式语言自动机(3)—— 三种有穷自动机_字符串_13都指扩充定义

(3)NFA接受的语言

给出NFA 形式语言自动机(3)—— 三种有穷自动机_有穷自动机_35

  • ​NFA接受的字符串​​​:若形式语言自动机(3)—— 三种有穷自动机_字符串_36,则称字符串x被M接受
  • ​被NFA接受的语言L(M)​​:被NFA M接受的全体字符串称为M接受的语言

三、具有ε转移的有穷自动机(ε-NFA)

(1)基本定义

  • ​具有ε转移的有穷自动机(ε-NFA)​​​:是一个五元组形式语言自动机(3)—— 三种有穷自动机_状态转移_18
  1. 其中Q,∑,q0,F的含义与一般的DFA或 NFA相同
  2. δ是映射形式语言自动机(3)—— 三种有穷自动机_有穷自动机_38
  • 说明:
  1. 和普通NFA相比,可能出现自发转移ε,即没有输入也有可能发生转移动作
  2. 这相比普通NFA增加了不确定性,加强了其表达能力。
  • 注意:
  1. n个字母表元素,NFA每个状态不一定有n个转移(出箭头),有些没定义,δ为Ø

(2)扩充定义

  1. ​ε-CLOSURE(q)​​:有ε-NFA,对于状态q,它的ε-CLOSURE(q)是:
  1. 形式化定义:
  1. q在ε-CLOSURE(q)中;
  2. 若p在ε-CLOSURE(q)中,则δ(p,ε)也都在ε-CLOSURE(q)中;
  3. 重复2,直到ε-CLOSURE(q)中状态不再增加为止。
  1. 进一步地,对于状态集P的ε-CLOSURE( P),我们规定:ε-CLOSURE( P) = ∪ε-CLOSURE(q),也就是所有元素的ε-CLOSURE并起来
  2. 从转移图上看,就是从状态q出发,沿着标有ε的有向边所能达到的一切状态所构成的集合(包括状态q本身)
  1. ​扩充转移函数​形式语言自动机(3)—— 三种有穷自动机_状态转移_08:扩展为映射 形式语言自动机(3)—— 三种有穷自动机_有穷自动机_22,定义如下:
  1. 形式语言自动机(3)—— 三种有穷自动机_字符串_41
  2. 形式语言自动机(3)—— 三种有穷自动机_字符串_41 (q,wa)=ε-CLOSURE( P), P = 形式语言自动机(3)—— 三种有穷自动机_状态转移_43(r,a),r∈形式语言自动机(3)—— 三种有穷自动机_字符串_41(q,w)(q∈Q, a∈∑, w∈∑*)
  • 这样理解:假设初始状态集是形式语言自动机(3)—— 三种有穷自动机_字符串_45,从第一个元素形式语言自动机(3)—— 三种有穷自动机_有穷自动机_46开始读串x,先扩展形式语言自动机(3)—— 三种有穷自动机_有穷自动机_46(读ε),然后对结果集合中每一个读第一个字符计算转移状态集,然后全部并(得形式语言自动机(3)—— 三种有穷自动机_有穷自动机_48),对所得集合中每个做ε扩展,再合并(至此得到形式语言自动机(3)—— 三种有穷自动机_有穷自动机_46读一个字符的结果),对结果集合中每一个读第二个字符计算转移状态集,然后求并/每个扩展/求并。重复“每个元素读入一个/求并/扩展/求并”,直到读完
  • 对于ε-NFA,形式语言自动机(3)—— 三种有穷自动机_字符串_50和`形式语言自动机(3)—— 三种有穷自动机_字符串_51必须要区分

(3)ε-NFA接受的语言:

给出ε-NFA 形式语言自动机(3)—— 三种有穷自动机_字符串_52,它接受的语言定义为:

  • ​被ε-NFA接受的语言L(M)​​​ :形式语言自动机(3)—— 三种有穷自动机_字符串_53

四、小结

  • DFA、NFA、ε-NFA表达能力依次提高,因为引入的不确定性越来越高。
  • 三者的接受能力没有变化,换句话说这三者是等价的


标签:状态,形式语言,NFA,有穷,自动机,DFA,转移,定义
From: https://blog.51cto.com/u_15887260/5876699

相关文章

  • 回文自动机
    回文自动机有些很优秀的性质。广义回文自动机你现在要对多个串建回文自动机,一个一个直接插进回文自动机里是对的。(也就是广义后缀自动机假掉的那种建法)例:LuoguP5555......
  • 【学习笔记】AC自动机常用技巧汇总
    \(\text{AC}\)自动机常用技巧汇总参考文章:自动机相关byAlex_Wei相关题目与题解:杂题20221.\(\text{AC}\)自动机上\(\text{dp}\)常用与限制长度与字典的字符串计数......
  • 3.4形式语言鸟瞰
    乔姆斯基于1956年建立形式语言体系,他把文法分成四种类型:0,1,2,3型与上下文无关文法一样,它们都由四部分组成但对产生式的限制有所不同G=(VT,VN,S,P)VT:终结......
  • AC自动机
    #include<cstdio>#include<cstring>#include<cstdio>#include<queue>#definemaxn1000039usingnamespacestd;chars[maxn],key[maxn];queue<int>q;inttrie[maxn][26]......
  • AC自动机
    AC自动机以trie为基础,首先将若干模式串插入trie树中,之后构建fail指针和AC自动机,即由trie树变为trie图。fail指针的定义是,对于当前点x,从根到x形成的字符串为s,x的fail指针指......
  • AC 自动机——trie 树与 KMP 算法的结合体
    默认所有字符串的下表从\(1\)开始。梗概与实现如果是单一的模式串和字符串进行匹配,KMP算法自然可以派上用场。但如果有多个模式串呢?对每个模式串都跑一遍KMP?如果有......
  • 【学习笔记】AC自动机
    AC自动机其实我将近三个月前就准备写这个并且随笔都建好了,但是一直咕咕到现在才写。其实记忆力好的同学应该意识到这篇其实8月份已经发过了,这次只是更新了一下发布日期而......
  • 伟大的 chy,请赐予我力量&chy 自动机的 SAM 做法
    https://www.luogu.com.cn/problem/U260001给定一组文本串,再每次给你一个询问串,求文本串的前缀集合中有多少串的border集合包含该询问串。考虑border也许会往kmp方......
  • 预告|AutoML Meetup V1 第四范式 & 百度 & AWS ,共探自动机器学习最佳实践
    自动机器学习(AutoML)是将机器学习应用于现实问题的端到端流程自动化的过程。随着机器学习部署场景的增多和机器学习算法的进步,AutoML的应用得到了进一步的发展。作为降低AI......
  • 回文自动机PAM从菜到菜
    回文自动机基础操作两个初始状态一个长度为\(0,-1\)的偶回文根和奇回文根。转移\(\delta(x,c)\)从\(x\)节点代表的回文串转移到两端加入字符\(c\)后到达的节点......