《形式语言与自动机理论电子教案-03》由会员分享，可在线阅读，更多相关《形式语言与自动机理论电子教案-03（146页珍藏版）》请在金锄头文库上搜索。
1、2018/9/3,1,第3章 有穷状态自动机,主要内容 确定的有穷状态自动机(DFA) 作为对实际问题的抽象、直观物理模型、形式定义，DFA接受的句子、语言，状态转移图。 不确定的有穷状态自动机(NFA) 定义； NFA与DFA的等价性；,2018/9/3,2,第3章 有穷状态自动机,带空移动的有穷状态自动机(-NFA) 定义。 -NFA与DFA的等价性。 FA是正则语言的识别器 正则文法(RG)与FA的等价性。 相互转换方法。 带输出的有穷状态自动机。 双向有穷状态自动机。,2018/9/3,3,第3章 有穷状态自动机,重点：DFA的概念，DFA、NFA、-NFA 、RG之间的等价转换思路与
2、方法。 难点：对DFA概念的理解，DFA、RG的构造方法， RG与FA的等价性证明。,2018/9/3,4,3.1 语言的识别,推导和归约中的回溯问题将对系统的效率产生极大的影响 SaA|aBAaA|cBaB|d 分析句子aaac 的过程中可能需要回溯。,2018/9/3,5,3.1 语言的识别,系统识别语言anc|n1and|n1的字符串过程中状态的变化图示如下：,2018/9/3,6,3.1 语言的识别,识别系统(模型) 系统具有有穷个状态，不同的状态代表不同的意义。按照实际的需要，系统可以在不同的状态下完成规定的任务。 我们可以将输入字符串中出现的字符汇集在一起构成一个字母表。系统处理的
3、所有字符串都是这个字母表上的字符串。,2018/9/3,7,3.1 语言的识别, 系统在任何一个状态(当前状态)下，从输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态。当前状态和新的状态可以是同一个状态，也可以是不同的状态；当系统从输入字符串中读入一个字符后，它下一次再读时，会读入下一个字符。这就是说，相当于系统维持有一个读写指针，该指针在系统读入一个字符后指向输入串的下一个字符。,2018/9/3,8,3.1 语言的识别, 系统中有一个状态，它是系统的开始状态，系统在这个状态下开始进行某个给定句子的处理。 系统中还有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一
4、个句子，把所有将系统从开始状态引导到这种状态的字符串放在一起构成一个语言，该语言就是系统所能识别的语言。,2018/9/3,9,3.1 语言的识别,相应的物理模型 一个右端无穷的输入带。 一个有穷状态控制器(finite state control,FSC) 。 一个读头。 系统的每一个动作由三个节拍构成：读入读头正注视的字符；根据当前状态和读入的字符改变有穷控制器的状态；将读头向右移动一格。,2018/9/3,10,3.1 语言的识别,有穷状态自动机的物理模型,2018/9/3,11,3.2有穷状态自动机,有穷状态自动机(finite automaton,FA) M=(Q，q0，F) Q状态
5、的非空有穷集合。qQ，q称为M的一个状态(state)。 输入字母表(Input alphabet)。输入字符串都是上的字符串。 q0q0Q，是M的开始状态(initial state)，也可叫做初始状态或者启动状态。,2018/9/3,12,3.2有穷状态自动机,状态转移函数(transition function)，有时候又叫做状态转换函数或者移动函数。：QQ，对(q，a)Q，(q，a)=p表示：M在状态q读入字符a，将状态变成p，并将读头向右移动一个带方格而指向输入字符串的下一个字符。 FFQ，是M的终止状态(final state)集合。qF，q称为M的终止状态，又称为接受状态(acc
6、ept state)。,2018/9/3,13,3.2有穷状态自动机,例 3-1 下面是一个有穷状态自动机 M1=(q0，q1，q2，0，1，q0，q2) 其中，1(q0,0)= q1，1(q1,0)= q2，1(q2,0)= q1 用表3-1表示1。,2018/9/3,14,3.2有穷状态自动机,M2=(q0，q1，q2，q3，0，1，2，2，q0，q2) 2(q0,0)= q1，2(q1,0)= q2 2(q2,0)= q1，2(q3,0)= q3 2(q0,1)= q3，2(q1,1)= q3 2(q2,1)= q3，2(q3,1)= q3 2(q0,2)= q3，2(q1,2)= q3
7、 2(q2,2)= q3，2(q3,2)= q3,2018/9/3,15,3.2有穷状态自动机,表3-2 2转换函数,2018/9/3,16,3.2有穷状态自动机,将扩充为,对任意的qQ，w*，a，定义,2018/9/3,17,3.2有穷状态自动机,两值相同，不用区分这两个符号。,2018/9/3,18,3.2有穷状态自动机,确定的有穷状态自动机 由于对于任意的qQ， a，(q，a)均有确定的值，所以，将这种FA称为确定的有穷状态自动机(deterministic finite automaton，DFA),2018/9/3,19,3.2有穷状态自动机,M接受(识别)的语言 对于x*如果(q，
8、w)F，则称x被M接受，如果(q，w)F，则称M不接受x。 L(M)=x| x*且(q，w)F 称为由M接受(识别)的语言 L(M1)= L(M2)=02n|n1 如果L(M1)=L(M2)，则称M1与M2等价。,2018/9/3,20,3.2有穷状态自动机,例 3-2 构造一个DFA，它接受的语言为x000y|x，y0，1* q0M的启动状态； q1M读到了一个0，这个0可能是子串“000”的第1个0； q2M在q1后紧接着又读到了一个0，这个0可能是子串“000”的第2个0； q3M在q2后紧接着又读到了一个0，发现输入字符串含有子串“000”；因此，这个状态应该是终止状态。,2018/9
9、/3,21,3.2有穷状态自动机,(q0,1)= q0M在q0读到了一个1，它需要继续在q0 “等待”可能是子串“000”的第1个0的输入字符0； (q1,1)= q0M在刚刚读到了一个0后，读到了一个1，表明在读入这个1之前所读入的0并不是子串“000”的第1个0，因此，M需要重新回到状态q0，以寻找子串“000”的第1个0；,2018/9/3,22,3.2有穷状态自动机,(q2,1)= q0M在刚刚发现了00后，读到了一个1，表明在读入这个1之前所读入的00并不是子串“000”的前两个0，因此，M需要重新回到状态q0，以寻找子串“000”的第1个0； (q3,0)= q3M找到了子串“00
10、0”，只用读入该串的剩余部分。 (q3,1)= q3M找到了子串“000”，只用读入该串的剩余部分。,2018/9/3,23,3.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),2018/9/3,24,3.2有穷状态自动机,一种更为直观的表示,2018/9/3,25,3.2有穷状态自动机,状态转移图(transition diagram) qQ q是该有向图中的一个顶点； (q，a)=p 图中有一
11、条从顶点q到顶点p的标记为a的弧； qF 标记为q的顶点被用双层圈标出； 用标有S的箭头指出M的开始状态。 状态转移图又可以叫做状态转换图。,2018/9/3,26,3.2有穷状态自动机,例 3-3构造一个DFA，它接受的语言为x000|x0，1*。 状态q0读到的0可能是输入字符串的最后三个0的第1个0； 在状态q1紧接着读到的0可能是输入字符串的最后三个0的第2个0； 在状态q2紧接着读到的0可能是输入字符串的最后三个0的第3个0；,2018/9/3,27,3.2有穷状态自动机,在状态q3紧接着读到的0也可能是输入字符串的最后三个0的第3个0； 如果在状态q1，q2，q3读到的是1，则要重
12、新检查输入串是否以三个0结尾。,2018/9/3,28,3.2有穷状态自动机,几点值得注意 定义FA时，常常只给出FA相应的状态转移图就可以了。 对于DFA来说，并行的弧按其上的标记字符的个数计算，对于每个顶点来说，它的出度恰好等于输入字母表中所含的字符的个数。,2018/9/3,29,3.2有穷状态自动机, 不难看出，字符串x被FA M接受的充分必要条件是，在M的状态转移图中存在一条从开始状态到某一个终止状态的有向路，该有向路上从第1条边到最后一条边的标记依次并置而构成的字符串x。简称此路的标记为x。 一个FA可以有多于1个的终止状态。,2018/9/3,30,3.2有穷状态自动机,接受语言
13、x000|x0，1*x001|x0，1*的FA,2018/9/3,31,3.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。,2018/9/3,32,3.2有穷状态自动机,Mn ：表示M从即时描述经过n次移动到达即时描述。 M存在即时描述1，2，n-1，使得 M 1，1M 2，n-1M 当n=0时，有=。即M 0 。 M + ：
14、表示M从即时描述经过至少1次移动到达即时描述。 M * ：表示M从即时描述经过若干步移动到达即时描述。,2018/9/3,33,3.2有穷状态自动机,当意义清楚时，我们将符号M、Mn、M*、M+中的M省去，分别用、n、*、+表示。,2018/9/3,34,3.2有穷状态自动机,对下图所示的DFA有如下的ID转换：,2018/9/3,35,3.2有穷状态自动机,q01010010001 1q0010010001 10q110010001 101q00010001 1010q1010001 10100q210001 101001q00001 1010010q1001 10100100q201,20
15、18/9/3,36,3.2有穷状态自动机, 101001000q31 1010010001q0 即 q0101001000110 1010010001q0q01010010001+ 1010010001q0q01010010001* 1010010001q0,2018/9/3,37,3.2有穷状态自动机,对于x*,q0x1+ x1q0q0x10+ x10q1q0x100+ x100q2q0x000+ x000q3,2018/9/3,38,3.2有穷状态自动机,能引导FA从开始状态到达q的字符串的集合为：set(q)=x | x*，(q0，x)=q 对图3-3所给的DFA 中的所有q，求set(
16、q)。,2018/9/3,39,set(q0)=x | x*，x=或者x以1结尾 set(q1)=x | x*，x=0或者x以10结尾 set(q2)=x | x*，x=00或者x以100结尾 set(q3)=x | x*，x以000结尾 set(q4)=x | x*， x以001结尾 这5个集合是两两互不相交。,2018/9/3,40,3.2有穷状态自动机,对于任意一个FA M=(Q，q0，F)我们可以按照如下方式定义关系RM： 对x，y*，xRMy qQ，使得xset(q)和yset(q)同时成立。 按照这个定义所得到的关系实际上是*上的一个等价关系。利用这个关系，可以将*划分成不多于|Q|个等价类。,
