自动机与形式语言_第三章_DFA_NFA

1、第第3章章 有穷状态自动机有穷状态自动机 主要内容主要内容 确定的有穷状态自动机确定的有穷状态自动机(DFA) 作为对实际问题的抽象、直观物理模型、形式作为对实际问题的抽象、直观物理模型、形式定义，定义，DFA接受的句子、语言，状态转移图。接受的句子、语言，状态转移图。 不确定的有穷状态自动机不确定的有穷状态自动机(NFA) 定义；定义； NFA与与DFA的等价性；的等价性；2022-3-171第第3章章 有穷状态自动机有穷状态自动机 带空移动的有穷状态自动机带空移动的有穷状态自动机(-NFA) 定义。定义。 -NFA与与DFA的等价性。的等价性。 FA是正则语言的识别器是正则语言的识别器 正

2、则文法正则文法(RG)与与FA的等价性。的等价性。 相互转换方法。相互转换方法。 带输出的有穷状态自动机。带输出的有穷状态自动机。 双向有穷状态自动机。双向有穷状态自动机。2022-3-172第第3章章 有穷状态自动机有穷状态自动机 重点：重点：DFA的概念，的概念，DFA、NFA、-NFA 、RG之间的等价转换思路与方法。之间的等价转换思路与方法。 难点：对难点：对DFA概念的理解，概念的理解，DFA、RG的构的构造方法，造方法， RG与与FA的等价性证明。的等价性证明。2022-3-173到目前为止，我们学了什么？到目前为止，我们学了什么？ 文法：语言的产生文法：语言的产生 RG, CFG

3、, CSG, PSG 对应的语言：RL, CFL, CSL, PSL FA：语言的识别：语言的识别2022-3-174RGRE-NFA NFADFA 正则语言正则语言 (RL)3.1 语言的识别语言的识别 推导和归约中的回溯问题将对系统的效率产推导和归约中的回溯问题将对系统的效率产生极大的影响生极大的影响 SaA|aB AaA|c BaB|d分析句子分析句子aaac 的过程中可能需要回溯。的过程中可能需要回溯。2022-3-1753.1 语言的识别语言的识别 系统识别语言系统识别语言anc|n1and|n1的字符的字符串过程中状态的变化图示如下：串过程中状态的变化图示如下： 2022-3-17

4、63.1 语言的识别语言的识别 识别系统识别系统(模型模型) 系统具有有穷个状态，不同的状态代表系统具有有穷个状态，不同的状态代表不同的意义。按照实际的需要，系统可以不同的意义。按照实际的需要，系统可以在不同的状态下完成规定的任务。在不同的状态下完成规定的任务。 我们可以将输入字符串中出现的字符汇我们可以将输入字符串中出现的字符汇集在一起构成一个字母表。系统处理的所集在一起构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串。有字符串都是这个字母表上的字符串。 2022-3-1773.1 语言的识别语言的识别 系统在任何一个状态系统在任何一个状态(当前状态当前状态)下，从下，从输入字符

5、串中读入一个字符，根据当前状输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态。当前态和读入的这个字符转到新的状态。当前状态和新的状态可以是同一个状态，也可状态和新的状态可以是同一个状态，也可以是不同的状态；当系统从输入字符串中以是不同的状态；当系统从输入字符串中读入一个字符后，它下一次再读时，会读读入一个字符后，它下一次再读时，会读入下一个字符。这就是说，相当于系统维入下一个字符。这就是说，相当于系统维持有一个读写指针，该指针在系统读入一持有一个读写指针，该指针在系统读入一个字符后指向输入串的下一个字符。个字符后指向输入串的下一个字符。 2022-3-1783.1 语言的识别

6、语言的识别 系统中有一个状态，它是系统的开始状系统中有一个状态，它是系统的开始状态，系统在这个状态下开始进行某个给定态，系统在这个状态下开始进行某个给定句子的处理。句子的处理。 系统中还有一些状态表示它到目前为止系统中还有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一个所读入的字符构成的字符串是语言的一个句子，把所有将系统从开始状态引导到这句子，把所有将系统从开始状态引导到这种状态的字符串放在一起构成一个语言，种状态的字符串放在一起构成一个语言，该语言就是系统所能识别的语言。该语言就是系统所能识别的语言。 2022-3-1793.1 语言的识别语言的识别 相应的物理模型相应的物理模

7、型一个右端无穷的输入带。一个右端无穷的输入带。一个有穷状态控制器一个有穷状态控制器(finite state control,FSC) 。一个读头。一个读头。 系统的每一个动作由三个节拍构成：读入系统的每一个动作由三个节拍构成：读入读头正注视的字符；根据当前状态和读入读头正注视的字符；根据当前状态和读入的字符改变有穷控制器的状态；将读头向的字符改变有穷控制器的状态；将读头向右移动一格。右移动一格。 2022-3-17103.1 语言的识别语言的识别 有穷状态自动机的物理模型有穷状态自动机的物理模型 2022-3-17113.2有穷状态自动机有穷状态自动机 有穷状态自动机有穷状态自动机(fini

8、te automaton,FA) M=(Q，q0，F)Q状态的非空有穷集合。状态的非空有穷集合。 qQ，q称为称为M的一个的一个状态状态(state)。输入字母表输入字母表(Input alphabet)。输入字。输入字符串都是符串都是上的字符串。上的字符串。 q0q0Q，是，是M的的开始状态开始状态(initial state)，也可叫做初始状态或者启动状态。也可叫做初始状态或者启动状态。2022-3-17123.2有穷状态自动机有穷状态自动机 状态状态转移函数转移函数(transition function)，有时候又叫做状态转换函数或者移动函数。有时候又叫做状态转换函数或者移动函数。：Q

9、Q，对，对 (q，a)Q，(q，a)=p表示：表示：M在状态在状态q读入字符读入字符a，将状态，将状态变成变成p，并将读头向右移动一个带方格而指，并将读头向右移动一个带方格而指向输入字符串的下一个字符。向输入字符串的下一个字符。FF Q，是，是M的的终止状态终止状态(final state)集集合。合。 qF，q称为称为M的的终止状态，终止状态，又称为又称为接受状态接受状态(accept state)。 2022-3-17133.2有穷状态自动机有穷状态自动机 例例 3-1 下面是一个有穷状态自动机下面是一个有穷状态自动机 M1=(q0，q1，q2，0，1，q0，q2)其中，其中，1(q0,0

10、)= q1，1(q1,0)= q2，1(q2,0)= q1 用表用表3-1表示表示1。状态说明状态说明状态状态输入字符输入字符0开始状态开始状态q0q1 q1q2终止状态终止状态q2q12022-3-17143.2有穷状态自动机有穷状态自动机 例例 3-1 下面是一个有穷状态自动机下面是一个有穷状态自动机 M1=(q0，q1，q2，0，1，q0，q2)其中，其中，1(q0,0)= q1，1(q1,0)= q2，1(q2,0)= q1 2022-3-17153.2有穷状态自动机有穷状态自动机 M2=(q0，q1，q2，q3，0，1，2，2，q0，q2)2(q0,0)= q1，2(q1,0)= q

11、22(q2,0)= q1，2(q3,0)= q32(q0,1)= q3，2(q1,1)= q32(q2,1)= q3，2(q3,1)= q32(q0,2)= q3，2(q1,2)= q32(q2,2)= q3，2(q3,2)= q3 2022-3-17163.2有穷状态自动机有穷状态自动机 状态说明状态说明状态状态输入字符输入字符012开始状态开始状态q0q1q3q3 q1q2q3q3终止状态终止状态q2q1q3q3 q3q3q3q3表表3-2 2转换函数转换函数 2022-3-17173.2有穷状态自动机有穷状态自动机 2022-3-17183.2有穷状态自动机有穷状态自动机 将将扩充为扩充

12、为QQ*:对任意的对任意的qQ，w*，a，定义，定义 ),(),()2(),() 1 (awqwaqqq2022-3-17193.2有穷状态自动机有穷状态自动机 ),(),(),(),(aqaqaqaq两值相同，不用区分这两个符号。两值相同，不用区分这两个符号。 2022-3-17203.2有穷状态自动机有穷状态自动机 确定的有穷状态自动机确定的有穷状态自动机 由于对于任意的由于对于任意的qQ， a，(q，a)均有均有确定的值，所以，将这种确定的值，所以，将这种FA称为称为确定的有穷状确定的有穷状态自动机态自动机(deterministic finite automaton，DFA) 2022

13、-3-17213.2有穷状态自动机有穷状态自动机 M接受接受(识别识别)的语言的语言 对于对于 x*如果如果(q，w)F，则称，则称x被被M接受，接受，如果如果(q，w) F，则称，则称M不接受不接受x。L(M)=x| x*且且(q，w)F称为由称为由M接受接受(识别识别)的语言的语言 如果如果L(M1)=L(M2)，则称，则称M1与与M2等价。等价。 L(M1)= L(M2)=02n|n1 2022-3-1722M1M223S10ACB100,1101是下面是下面DFA语言中的字符串。语言中的字符串。从从A出发：出发：3.2有穷状态自动机有穷状态自动机 例子: 识别语言中的串24101是下面

14、是下面DFA语言中的字符串。语言中的字符串。跟随标记为跟随标记为1的弧的弧3.2有穷状态自动机有穷状态自动机 例子: 识别语言中的串Start10ACB100,125101是下面是下面DFA语言中的字符串。语言中的字符串。从从B出发，跟随标记为出发，跟随标记为0的弧的弧3.2有穷状态自动机有穷状态自动机 例子: 识别语言中的串Start10ACB100,126101是下面是下面DFA语言中的字符串。语言中的字符串。最后从最后从A出发，跟随标记为出发，跟随标记为1的弧，达到接的弧，达到接受状态受状态B，所以，所以101是该语言的字符串。是该语言的字符串。3.2有穷状态自动机有穷状态自动机 例子:

15、 识别语言中的串Start10ACB100,1273.2有穷状态自动机有穷状态自动机 该例子中DFA对应的语言为：w | w 0,1* 且 w 不包含连续的两个1。S10ACB100,128 等价性证明 我们经常需要证明两个集合等价 这里，一个集合是 “该DFA接收的语言” 另一个集合是 “w | w 0,1* 且 w 不包含连续的两个1”3.2有穷状态自动机有穷状态自动机 S10ACB100,129证明集合S=T, 需要证明: S T and T S:如果w在集合S中, 那么w在集合T中；如果w在集合T中, 那么w在集合S中。1. 设S = “该DFA接收的语言”, T = “不包含连续的1

16、”3.2有穷状态自动机有穷状态自动机 S10ACB100,130 Part 1: S T 证明: if w 被该DFA接受，那么w 不包含连续的1. 按照w的长度归纳证明。3.2有穷状态自动机有穷状态自动机 S10ACB100,131归纳假设：归纳假设： 如果(A, w) = A, 那么w 没有连续的1并且不以1结尾. 如果(A, w) = B, 那么w 没有连续的1并且以单个1结尾.Basis: |w| = 0; i.e., w = .(1) 成立，因为 未有任何元素1. (2) 成立，因为 (A, ) 不等同于B3.2有穷状态自动机有穷状态自动机 S10ACB100,1归纳步骤归纳步骤13

17、2 假设|x| 长度为n，且(1)和(2)对于x成立 证明w = xa, |w|=n+1时(1)和(2)成立3.2有穷状态自动机有穷状态自动机 S10ACB100,1归纳步骤归纳步骤233 (1) 如果(A, w) = A。因为w = xa，由DFA可知，(A, x) 必须是A或者B, a必须是0. 根据归纳假设, x不包含11. 因此w不包含11，也不以1结尾，假设（1）对w成立。S10ACB100,13.2有穷状态自动机有穷状态自动机 归纳步骤归纳步骤234 (2)如果(A, w) = B。因为w = xa，由DFA可知，(A, x) 必须是A, a必须是1。 根据归纳假设, x不包含11

18、并且不以1结尾。 因此，w没有连续的1并且以单个1结尾，归纳假设（2）对w成立.3.2有穷状态自动机有穷状态自动机 S10ACB100,1归纳步骤归纳步骤235 Part 2: S T 下面我们需要证明, 如果w不包含连续的1, 那么w被该DFA接受。 换言之: 如果w不被该DFA接受，则w一定包含连续的1“if X then Y”=“if not Y then not X.”3.2有穷状态自动机有穷状态自动机 S10ACB100,136 w不被DFA接收的充要条件是(A, w) = C. 因此, w = x1y, x引导DFA到B, 1引导DFA到C,y是到达C以后产生的后缀。 如果(A,x

19、) = B，根据之前的证明，x以单个1结尾，因此x = z1（z为不包含11的前缀） 因此, w = z11y，包含连续的1, 得证。3.2有穷状态自动机有穷状态自动机 S10ACB100,13.2有穷状态自动机有穷状态自动机 例例 3-2 构造一个构造一个DFA，它接受的语言为，它接受的语言为x000y|x，y0，1*q0M的启动状态；的启动状态；q1M读到了一个读到了一个0，这个，这个0可能是子串可能是子串“000”的的第第1个个0；q2M在在q1后紧接着又读到了一个后紧接着又读到了一个0，这个，这个0可能可能是子串是子串“000”的第的第2个个0；q3M在在q2后紧接着又读到了一个后紧接

20、着又读到了一个0，发现输入字，发现输入字符串含有子串符串含有子串“000”；因此，这个状态应该是终；因此，这个状态应该是终止状态。止状态。2022-3-17373.2有穷状态自动机有穷状态自动机 (q0,1)= q0M在在q0读到了一个读到了一个1，它需要，它需要继续在继续在q0 “等待等待”可能是子串可能是子串“000”的第的第1个个0的输入字符的输入字符0；(q1,1)= q0M在刚刚读到了一个在刚刚读到了一个0后，读后，读到了一个到了一个1，表明在读入这个，表明在读入这个1之前所读入之前所读入的的0并不是子串并不是子串“000”的第的第1个个0，因此，因此，M需要重新回到状态需要重新回到

21、状态q0，以寻找子串，以寻找子串“000”的的第第1个个0；2022-3-17383.2有穷状态自动机有穷状态自动机 (q2,1)= q0M在刚刚发现了在刚刚发现了00后，读到了后，读到了一个一个1，表明在读入这个，表明在读入这个1之前所读入的之前所读入的00并并不是子串不是子串“000”的前两个的前两个0，因此，因此，M需要重需要重新回到状态新回到状态q0，以寻找子串，以寻找子串“000”的第的第1个个0；(q3,0)= q3M找到了子串找到了子串“000”，只用读，只用读入该串的剩余部分。入该串的剩余部分。(q3,1)= q3M找到了子串找到了子串“000”，只用读，只用读入该串的剩余部分

22、。入该串的剩余部分。2022-3-17393.2有穷状态自动机有穷状态自动机 M=(q0，q1，q2，q3，0，1， (q0,0)= q1，(q1,0)= q2，(q2,0)= q3，(q0,1)= q0，(q1,1)= q0，(q2,1)= q0，(q3,0)= q3，(q3,1)= q3，q0，q3) 状态说明状态说明状态状态输入字符输入字符01开始状态开始状态q0q1q0 q1q2q0 q2q3q0终止状态终止状态q3q3q32022-3-17403.2有穷状态自动机有穷状态自动机 一种更为直观的表示一种更为直观的表示2022-3-17413.2有穷状态自动机有穷状态自动机 例例 3-3

23、构造一个构造一个DFA，它接受的语言为，它接受的语言为x000|x0，1*。 状态状态q0读到的读到的0可能是输入字符串的最后三个可能是输入字符串的最后三个0的第的第1个个0； 在状态在状态q1紧接着读到的紧接着读到的0可能是输入字符串的最可能是输入字符串的最后三个后三个0的第的第2个个0； 在状态在状态q2紧接着读到的紧接着读到的0可能是输入字符串的最可能是输入字符串的最后三个后三个0的第的第3个个0；2022-3-17423.2有穷状态自动机有穷状态自动机 在状态在状态q3紧接着读到的紧接着读到的0也可能是输入字符串的也可能是输入字符串的最后三个最后三个0的第的第3个个0； 如果在状态如果

24、在状态q1，q2，q3读到的是读到的是1，则要重新检，则要重新检查输入串是否以三个查输入串是否以三个0结尾。结尾。 2022-3-17433.2有穷状态自动机有穷状态自动机 几点值得注意几点值得注意 定义定义FA时，常常只给出时，常常只给出FA相应的状态转相应的状态转移图就可以了。移图就可以了。 对于对于DFA来说，并行的弧按其上的标记字来说，并行的弧按其上的标记字符的个数计算，对于每个顶点来说，它的符的个数计算，对于每个顶点来说，它的出度恰好等于输入字母表中所含的字符的出度恰好等于输入字母表中所含的字符的个数。个数。 2022-3-17443.2有穷状态自动机有穷状态自动机 不难看出，字符串

25、不难看出，字符串x被被FA M接受的充分必接受的充分必要条件是，在要条件是，在M的状态转移图中存在一条的状态转移图中存在一条从开始状态到某一个终止状态的有向路，从开始状态到某一个终止状态的有向路，该有向路上从第该有向路上从第1条边到最后一条边的标记条边到最后一条边的标记依次并置而构成的字符串依次并置而构成的字符串x。简称此路的标。简称此路的标记为记为x。 一个一个FA可以有多于可以有多于1个的终止状态。个的终止状态。 2022-3-17453.2有穷状态自动机有穷状态自动机 例例 3-4 构造一个构造一个DFA，它接受的语言，它接受的语言为为0n1m2k|n,m,k1。 q0M的启动状态；的启

26、动状态；q1M读到至少一个读到至少一个0，并等待读更多的，并等待读更多的0；q2M读到至少一个读到至少一个0后，读到了至少一个后，读到了至少一个1，并等待读更多的，并等待读更多的1；q3M读到至少一个读到至少一个0后跟至少一个后跟至少一个1后，后，并且接着读到了至少一个并且接着读到了至少一个2。 2022-3-17463.2有穷状态自动机有穷状态自动机 先设计先设计“主体框架主体框架”再补充细节再补充细节2022-3-1747 3.2有穷状态自动机有穷状态自动机 当当FA一旦进入状态一旦进入状态qt，它就无法离开此状，它就无法离开此状态。所以，态。所以，qt相当于一个陷阱状态相当于一个陷阱状态

27、(trap)。一般地，我们将陷阱状态用作在其他状态一般地，我们将陷阱状态用作在其他状态下发现输入串不可能是该下发现输入串不可能是该FA所识别的语言所识别的语言的句子时进入的状态。在此状态下，的句子时进入的状态。在此状态下，FA读读完输入串中剩余的字符。完输入串中剩余的字符。 2022-3-17483.2有穷状态自动机有穷状态自动机 在构造一个识别给定语言的在构造一个识别给定语言的FA时，用画时，用画图的方式比较方便、直观。我们可以先根图的方式比较方便、直观。我们可以先根据语言的主要特征画出该据语言的主要特征画出该FA的的“主体框主体框架架”，然后再去考虑画出一些细节要求的，然后再去考虑画出一些

28、细节要求的内容。内容。2022-3-17493.2有穷状态自动机有穷状态自动机 FA的状态具有一定的记忆功能：不同的状的状态具有一定的记忆功能：不同的状态对应于不同的情况，由于态对应于不同的情况，由于FA只有有穷个只有有穷个状态，所以，在识别一个语言的过程中，状态，所以，在识别一个语言的过程中，如果有无穷种情况需要记忆，我们肯定是如果有无穷种情况需要记忆，我们肯定是无法构造出相应的无法构造出相应的FA的。的。 2022-3-17503.2有穷状态自动机有穷状态自动机 例例 3-5构造一个构造一个DFA，它接受的语言，它接受的语言为为x|x0，1*，且当把，且当把x看成二进制看成二进制数时，数时

29、，x模模3与与0同余同余。 q0对应除以对应除以3余数为余数为0的的x组成的等价类；组成的等价类； q1对应除以对应除以3余数为余数为1的的x组成的等价类；组成的等价类； q2对应除以对应除以3余数为余数为2的的x组成的等价类；组成的等价类； qsM的开始状态。的开始状态。2022-3-17513.2有穷状态自动机有穷状态自动机 qs在此状态下读入在此状态下读入0时，有时，有x=0，所以应，所以应该进入状态该进入状态q0；读入；读入1时，有时，有x=1，所以应，所以应该进入状态该进入状态q1。即：。即：(qs，0)= q0；(qs，1)= q1 。2022-3-17523.2有穷状态自动机有穷

30、状态自动机 q0能引导能引导M到达此状态的到达此状态的x除以除以3余余0，所以有：所以有：x=3*n+0。 读入读入0时，引导时，引导M到达下一个状态的字符串到达下一个状态的字符串为为x0，x0=2*(3*n+0)=3*2*n+0。所以，。所以，(q0，0)= q0； 读入读入1时，时，M到达下一个状态的字符串为到达下一个状态的字符串为x1，x1=2*(3*n+0)+1=3*2*n+1。所以，。所以，(q0，1)= q1；2022-3-17533.2有穷状态自动机有穷状态自动机 q1能引导能引导M到达此状态的到达此状态的x除以除以3余余1，所以有：所以有：x=3*n+1。 读入读入0时，引导时

31、，引导M到达下一个状态的字符串到达下一个状态的字符串为为x0，x0=2*(3*n+1)=3*2*n+2。所以即：。所以即：(q1，0)= q2； 读入读入1时，引导时，引导M到达下一个状态的字符串到达下一个状态的字符串为为x1，x1=2*(3*n+1)+1=3*2*n+2+1=3*(2*n+1)。所以所以(q1，1)= q0 2022-3-17543.2有穷状态自动机有穷状态自动机 q2能引导能引导M到达此状态的到达此状态的x除以除以3余余2，所以：，所以：x=3*n+2。 读入读入0时，引导时，引导M到达下一个状态的字符串为到达下一个状态的字符串为x0，x0=2*(3*n+2)=3*2*n+

32、4=3*(2*n+1)+1。所以。所以(q2，0)= q1； 读入读入1时，引导时，引导M到达下一个状态的字符串为到达下一个状态的字符串为x1，x1=2*(3*n+2)+1=3*2*n+4+1=3*(2*n+1)+2。所以，。所以，(q2，1)= q2 。2022-3-17553.2有穷状态自动机有穷状态自动机 接受语言接受语言x|x0，1*，且当把，且当把x看成二进看成二进制数时，制数时，x模模3与与0同余同余的的DFA如下：如下： 2022-3-17563.2有穷状态自动机有穷状态自动机 例例 3-6 构造一个构造一个DFA，它接受的语言，它接受的语言L=x|x0，1*，且对，且对x中任意

33、一个中任意一个长度不大于长度不大于5的子串的子串a1a2an，a1+a2+an3，n5 。 输入串为输入串为 a1a2aiai+4ai+5am2022-3-17573.2有穷状态自动机有穷状态自动机 当当i=1，2，3，也就是，也就是M读到输入串的第读到输入串的第1、2、3个字符时，它需要将这些字符记下来。个字符时，它需要将这些字符记下来。因为因为a1ai可能需要用来判定输入串的最可能需要用来判定输入串的最初初45个字符组成的子串是否满足语言的要个字符组成的子串是否满足语言的要求。求。 当当i=4，5，也就是，也就是M读到输入串的第读到输入串的第4、5个个字符时，在字符时，在a1+a2+ai3

34、的情况下，的情况下，M需要将需要将a1ai记下来；在记下来；在a1+a2+ai3时，时，M应该进入陷阱状态应该进入陷阱状态qt。 2022-3-17583.2有穷状态自动机有穷状态自动机 当当i=6，也就是，也就是M读到输入串的第读到输入串的第6个字符，个字符，此时，以前读到的第此时，以前读到的第1个字符个字符a1就没有用了，就没有用了，此时它要看此时它要看a2+a3+a63是否成立，如果是否成立，如果成立，成立，M需要将需要将a2a6记下来；在记下来；在a2+a3+ai3时，时，M应该进入陷阱状态应该进入陷阱状态qt。 2022-3-17593.2有穷状态自动机有穷状态自动机 当当M完成对子

35、串完成对子串a1a2aiai+4的考察，并发的考察，并发现它满足语言的要求时，现它满足语言的要求时，M记下来的是记下来的是aiai+4，此时它读入输入串的第，此时它读入输入串的第i+5个字符个字符ai+5，以前读到的第，以前读到的第i个字符个字符ai就没有用了，就没有用了，此时它要看此时它要看ai+1+ai+2+ai+53是否成立，是否成立，如果成立，如果成立，M需要将需要将ai+1，ai+2，ai+5记下记下来；在来；在ai+1+ai+2+ai+53时，时，M应该进入陷应该进入陷阱状态阱状态qt。 2022-3-17603.2有穷状态自动机有穷状态自动机 M需要记忆的内容有：需要记忆的内容有

36、： 什么都未读入什么都未读入20=1种；种； 记录有记录有1个字符个字符21=2种；种； 记录有记录有2个字符个字符22=4种；种； 记录有记录有3个字符个字符23=8种；种； 记录有记录有4个字符个字符24-1=15种；种； 记录有记录有5个字符个字符25-6=26种；种； 记录当前的输入串不是句子记录当前的输入串不是句子1种。种。 2022-3-17613.2有穷状态自动机有穷状态自动机状态设置状态设置qM还未读入任何字符；还未读入任何字符；qt陷阱状态；陷阱状态；qa1a2aiM记录有记录有i个字符，个字符，1i5。a1，a2，ai0，1。取取DFA M=(Q，0，1，q，F)F= q

37、qa1a2ai| a1，a2，ai0，1且且1i5且且a1+a2+ai3Q=qt F 2022-3-17623.2有穷状态自动机有穷状态自动机 (q，a1)=qa1 (qa1，a2)=qa1a2 (qa1a2，a3)=qa1a2a3 qa1a2a3a如果a1+a2+a3+a3(qa1a2a3，a)= qt如果a1+a2+a3+a3 2022-3-17633.2有穷状态自动机有穷状态自动机 qa1a2a3a4a 如果a1+a2+a3+a4+a3(qa1a2a3a4，a)= qt如果a1+a2+a3+a4+a3qa2a3a4a5a a2+a3+a4+ a5+a3(qa1a2a3a4a5，a)=qt

38、如果a2+a3+a4+ a5+a3(qt，a1)=qt2022-3-17643.2有穷状态自动机有穷状态自动机 接受语言接受语言x000|x0，1*x001|x0，1*的的FA 2022-3-17653.2有穷状态自动机有穷状态自动机 能引导能引导FA从开始状态到达从开始状态到达q的字符串的集合为：的字符串的集合为：set(q)=x | x*，(q0，x)=q对图对图3-5所给的所给的DFA 中的所有中的所有q，求，求set(q)。2022-3-1766set(q0)=x | x*，x=或者或者x以以1但不是但不是001结尾结尾set(q1)=x | x*，x=0或者或者x以以10结尾结尾se

39、t(q2)=x | x*，x=00或者或者x以以100结尾结尾set(q3)=x | x*，x以以000结尾结尾set(q4)=x | x*， x以以001结尾结尾这这5个集合是两两互不相交。个集合是两两互不相交。 2022-3-17673.2有穷状态自动机有穷状态自动机 对于任意一个对于任意一个FA M=(Q，q0，F)我们可以按照如下方式定义关系我们可以按照如下方式定义关系RM： 对对 x，y*，xRMy qQ，使得，使得xset(q)和和yset(q)同时成立。同时成立。 按照这个定义所得到的关系实际上是按照这个定义所得到的关系实际上是*上上的一个等价关系。利用这个关系，可以将的一个等价

40、关系。利用这个关系，可以将*划分成不多于划分成不多于|Q|个等价类。个等价类。 2022-3-17683.2有穷状态自动机有穷状态自动机 即时描述即时描述(instantaneous description，ID ） x，y*，(q0，x)=q, xqy称为称为M的一个的一个即即时描述，时描述，表示表示xy是是M正在处理的一个字符串，正在处理的一个字符串，x引导引导M从从q0启动并到达状态启动并到达状态q，M当前正注视当前正注视着着y的首字符。的首字符。 如果如果xqay是是M的一个即时描述，且的一个即时描述，且(q，a)=p，则则xqay M xapy。 2022-3-17693.2有穷状态

41、自动机有穷状态自动机 Mn ：表示：表示M从即时描述从即时描述经过经过n次移动到次移动到达即时描述达即时描述。 M存在即时描述存在即时描述1，2，n-1，使得，使得 M 1，1M 2，n-1M 当当n=0n=0时，有时，有=。即。即M M 0 0 。 M M + + ：表示：表示M M从即时描述从即时描述经过至少经过至少1 1次移动到次移动到达即时描述达即时描述。 M M * * ：表示：表示M M从即时描述从即时描述经过若干步移动经过若干步移动到达即时描述到达即时描述。 2022-3-17703.2有穷状态自动机有穷状态自动机 当意义清楚时，我们将符号当意义清楚时，我们将符号M、Mn、M*、

42、M+中的中的M省去，分别用省去，分别用、n、*、+表示。表示。 2022-3-17713.2有穷状态自动机有穷状态自动机 对下图所示的对下图所示的DFA有如下的有如下的ID转换：转换：2022-3-17723.2有穷状态自动机有穷状态自动机 q01010010001 1q0010010001 10q110010001 101q00010001 1010q1010001 10100q210001 101001q00001 1010010q1001 10100100q201 2022-3-17733.2有穷状态自动机有穷状态自动机 101001000q31 1010010001q0即 q01010

43、01000110 1010010001q0 q01010010001+ 1010010001q0 q01010010001* 1010010001q0 2022-3-17743.2有穷状态自动机有穷状态自动机 对于x*, q0 x1+ x1q0 q0 x10+ x10q1 q0 x100+ x100q2 q0 x000+ x000q3 2022-3-17753.3 NFA 3.3.1 作为对作为对DFA的修改的修改 希望是接受希望是接受x|x0，1*，且，且x含有子串含有子串00或或11的的FA如下：如下：2022-3-17763.3.1 作为对作为对DFA的修改的修改 希望是接受希望是接受x

44、|x0，1*，且，且x 的倒数第的倒数第10个字符为个字符为1的的FA如下如下 ：2022-3-17773.3.1 作为对作为对DFA的修改的修改 这两个图所给的这两个图所给的“FA”与前面我们所定义与前面我们所定义的的FA，即，即DFA，的区别在于：，的区别在于： 并不是对于所有的并不是对于所有的(q，a)Q,(q，a)都有一个状态与它对应；都有一个状态与它对应； 并不是对于所有的并不是对于所有的(q，a)Q,(q，a)只对应一个状态。只对应一个状态。 “FA”在任意时刻可以处于有穷多个状态。在任意时刻可以处于有穷多个状态。 “FA”具有具有“智能智能”。2022-3-17783.3.2 N

45、FA的形式定义的形式定义 不确定的有穷状态自动机不确定的有穷状态自动机(non-deterministic finite automaton ,NFA) M是一个五元组是一个五元组M=(Q，q0，F) Q、q0、F的意义同的意义同DFA。 ：Q2Q，对，对 (q，a)Q，(q，a)= p1，p2，pm表示表示M在状态在状态q读入字符读入字符a，可，可以选择地将状态变成以选择地将状态变成p1、或者、或者p2、或者、或者pm ，并将读头向右移动一个带方格而指向输入字符并将读头向右移动一个带方格而指向输入字符串的下一个字符。串的下一个字符。 2022-3-17793.3.2 NFA的形式定义的形式定

46、义 FA的状态转移图、的状态转移图、FA的状态对应的等价类、的状态对应的等价类、FA的即时描述对的即时描述对NFA都有效。都有效。 接受接受x|x0，1*，且，且x含有子串含有子串00或或11的的FA对应的移动函数定义表。对应的移动函数定义表。2022-3-17803.3.2 NFA的形式定义的形式定义 状态说明状态说明状态状态输入字符输入字符01启动状态启动状态q0q0，q1 q0，q2 q1q3 q2q3终止状态终止状态q3q3q32022-3-17813.3.2 NFA的形式定义的形式定义 接受接受x|x0，1*，且，且x 的倒数第的倒数第10个字符个字符为为1的的FA对应的移动函数定义

47、表。对应的移动函数定义表。2022-3-17823.3.2 NFA的形式定义的形式定义 状态说明状态说明状态状态输入字符输入字符01启动状态启动状态q0q0 q0，q1 q1q2q2 q2q3q3 q3q4q4 q4q5q5 q5q6q6 q6q7q7 q7q8q8 q8q9 q9 q9q10 q10终止状态终止状态q102022-3-17833.3.2 NFA的形式定义的形式定义 将将扩充为扩充为QQ2:*对任意的对任意的qQ，w*，a，定义，定义 a)，(rp，使得w)，(q r|p),()2(),()1 (waqqq2022-3-17843.3.2 NFA的形式定义的形式定义 M接受接受

48、(识别识别)的语言的语言 对于对于 x*，如果如果(q0，w) F，则称则称x被被M接受，如果接受，如果(q0，w)F=，则称则称M不接受不接受x。L(M)=x| x*且且(q0，w) F，称为由称为由M接受接受(识别识别)的语言。的语言。 2022-3-178586DFA例子: Chessboard1257934861rbb42153751397 r b2,4 54,6 1,3,52,6 52,8 1,5,72,4,6,8 1,3,7,92,8 3,5,94,8 54,6 5,7,916,8 5包含了终止状态，接收启动状态启动状态终止状态终止状态873.3.3 NFA与与DFA等价等价 任意

49、任意DFA可以转换成接收相同语言的可以转换成接收相同语言的NFA。 如果DFA中有D(q, a) = p, 在NFA中使得 N(q, a) = p. 那么NFA总与DFA读取输入后处于相同的状态。 DFANFA88 类似的，对于任意NFA，可以找到一个对应的DFA接收相同的语言。 证明方法：子集构造（subset construction）。3.3.3 NFA与与DFA等价等价 NFADFA3.3.3 NFA与与DFA等价等价 对于一个输入字符，对于一个输入字符，NFA与与DFA的差异是的差异是前者可以进入若干个状态，而后者只能进前者可以进入若干个状态，而后者只能进入一个惟一的状态。虽然从入一

50、个惟一的状态。虽然从DFA看待问题看待问题的角度来说，的角度来说，NFA在某一时刻同时进入若在某一时刻同时进入若干个状态，但是，这若干个状态合在一起干个状态，但是，这若干个状态合在一起的的“总效果总效果”相当于它处于这些状态对应相当于它处于这些状态对应的一个的一个“综合状态综合状态”。因此，我们考虑让。因此，我们考虑让DFA用一个状态去对应用一个状态去对应NFA的一组状态。的一组状态。 2022-3-17892022-3-1790状态说明状态说明状态状态输入字符输入字符01启动状态启动状态q0q0，q1 q0，q2 q1q3 q2q3终止状态终止状态q3q3q33.3.3 NFA与与DFA等价

51、等价 q0，q1q0，q2q03.3.3 NFA与与DFA等价等价 NFA M1=(Q，1，q0，F1)与与DFA M2=(Q2，2，q0，F2)的对应关系：的对应关系： NFA从开始状态从开始状态q0启动，我们就让相应的启动，我们就让相应的DFA从状态从状态q0启动。所以启动。所以q0= q0。 对于对于NFA 的一个状态组的一个状态组q1，q2，qn，如，如果果NFA在此状态组时在此状态组时读入字符读入字符a后可以后可以进入状进入状态组态组p1，p2，pm,则让相应的则让相应的DFA在状态在状态q1，q2，qn读入字符读入字符a时，时，进入状态进入状态p1，p2，pm。 2022-3-17

52、911=(=(q1，q2，qn,a)=)= p1，p2，pm 2=(=(q1，q2，qn,a)=)= p1，p2，pm 92子集构造: Subset Construction r b2,4 54,6 1,3,52,6 52,8 1,5,72,4,6,8 1,3,7,92,8 3,5,94,8 54,6 5,7,916,8 5*r b12,4 51=(=(q1，q2，qn,a)=)= p1，p2，pm 2=(=(q1，q2，qn,a)=)= p1，p2，pm 93子集构造: Subset Construction r b2,4 54,6 1,3,52,6 52,8 1,5,72,4,6,8 1,

53、3,7,92,8 3,5,94,8 54,6 5,7,916,8 5*r b12,4 52,451=(=(q1，q2，qn,a)=)= p1，p2，pm 2=(=(q1，q2，qn,a)=)= p1，p2，pm 94子集构造: Subset Construction r b2,4 54,6 1,3,52,6 52,8 1,5,72,4,6,8 1,3,7,92,8 3,5,94,8 54,6 5,7,916,8 5*1=(=(q1，q2，qn,a)=)= p1，p2，pm 2=(=(q1，q2，qn,a)=)= p1，p2，pm r b12,4,6,852,42,4,6,8 1,3,5,71,

54、3,5,72,4 595子集构造: Subset Construction r b2,4 54,6 1,3,52,6 52,8 1,5,72,4,6,8 1,3,7,92,8 3,5,94,8 54,6 5,7,916,8 5*1=(=(q1，q2，qn,a)=)= p1，p2，pm 2=(=(q1，q2，qn,a)=)= p1，p2，pm r b1 * 1,3,7,92,4,6,82,4,6,8 1,3,7,952,42,4,6,8 1,3,5,71,3,5,72,4 596子集构造: Subset Construction r b2,4 54,6 1,3,52,6 52,8 1,5,72,

55、4,6,8 1,3,7,92,8 3,5,94,8 54,6 5,7,916,8 5*1=(=(q1，q2，qn,a)=)= p1，p2，pm 2=(=(q1，q2，qn,a)=)= p1，p2，pm r b1 * 1,3,5,7,9 * 1,3,7,92,4,6,8 1,3,5,7,92,4,6,82,4,6,8 1,3,7,952,42,4,6,8 1,3,5,71,3,5,72,4 597子集构造: Subset Construction r b2,4 54,6 1,3,52,6 52,8 1,5,72,4,6,8 1,3,7,92,8 3,5,94,8 54,6 5,7,916,8 5

56、*1=(=(q1，q2，qn,a)=)= p1，p2，pm 2=(=(q1，q2，qn,a)=)= p1，p2，pm r b1 * 1,3,5,7,9 * 1,3,7,92,4,6,8 1,3,5,7,92,4,6,82,4,6,8 1,3,7,952,42,4,6,8 1,3,5,71,3,5,72,4 52,4,6,8 1,3,5,7,998子集构造: Subset Construction r b2,4 54,6 1,3,52,6 52,8 1,5,72,4,6,8 1,3,7,92,8 3,5,94,8 54,6 5,7,916,8 5*1=(=(q1，q2，qn,a)=)= p1，p

57、2，pm 2=(=(q1，q2，qn,a)=)= p1，p2，pm r b1 * 1,3,5,7,9 * 1,3,7,92,4,6,8 52,4,6,8 1,3,5,7,92,4,6,82,4,6,8 1,3,7,952,42,4,6,8 1,3,5,71,3,5,72,4 52,4,6,8 1,3,5,7,999Example: Subset Construction r b2,4 54,6 1,3,52,6 52,8 1,5,72,4,6,8 1,3,7,92,8 3,5,94,8 54,6 5,7,916,8 5*r b1 * 1,3,5,7,92,4,6,8 1,3,5,7,9 * 1

58、,3,7,92,4,6,8 52,4,6,8 1,3,5,7,92,4,6,82,4,6,8 1,3,7,952,42,4,6,8 1,3,5,71,3,5,72,4 52,4,6,8 1,3,5,7,91=(=(q1，q2，qn,a)=)= p1，p2，pm 2=(=(q1，q2，qn,a)=)= p1，p2，pm 3.3.3 NFA与与DFA等价等价 定理定理 3-1 NFA与与DFA等价。等价。证明：证明：构造与构造与M1等价的等价的DFA M2 。 M1=(Q，1，q0，F1) M2=(Q2，2，q0，F2) Q2=2Q F2=p1，p2，pm|p1，p2，pm Q&p1，p2

59、，pmF1 2022-3-171003.3.3 NFA与与DFA等价等价 2(q1，q2，qn，a)=p1，p2，pm1(q1，q2，qn，a)= p1，p2，pm (2) 证明证明1(q0，x)= p1，p2，pm 2(q0，x)=p1，p2，pm。 设设x*，施归纳于，施归纳于|x| x=，1(q0，)= q0,2(q0，)=q0 2022-3-171013.3.3 NFA与与DFA等价等价 设当设当|x|=n是结论成立。下面证明当是结论成立。下面证明当|x|=n+1是结是结论也成立。不妨设论也成立。不妨设x=wa，|w|=n，a 1 1(q(q0 0，wa)=wa)=1 1( (1 1(q(q0 0，w)w)，