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