形式语言与自动机.doc

形式语言与自动机（计算机网络班）第一章 绪论1. 幂集 2. 字母表的性质3. 真前缀、真后缀、前缀、后缀4. 语言的形式化表示题目：填空题,的幂集是：,判断题对于任何一个非空集合A, A2A 错误a,d,fa,b,c,z是字母表 正确一定是字符串的前缀或后缀，当字符串不为时，则一定是其真前缀或真后缀 正确=aa,ab,bb,ba，求字符串aaaaabbbba的所有前缀的集合、后缀的集合、真前缀的集合、真后缀的集合。解：由前缀、后缀、真前缀、真后缀的集合可以有：其前缀集合为：,aa,aaaa,aaaaab,aaaaabbb,aaaaabbbba其真前缀集合为：,aa,aaaa,aaaaab,aaaaabbb其后缀集合为：,ba,bbba,abbbba, aaabbbba, aaaaabbbba 其真后缀集合为：,ba,bbba,abbbba, aaabbbba设，请给出上的下列语言的形式表示。所有最多有一对连续的0或者最多有一对连续的1的串。解答：。所有最多有一对连续的0并且最多有一对连续的1的串。解答：按照实际情况分成4类：1) 只有一对连续的0： 。2) 只有一对连续的1： 。3) 没有连续的0并且没有连续的1：。4) 有一对连续的0和一对连续的1：。所有长度为偶数的串。 解答：所有倒数第10个字符是0的串。 解答：0,100,1。第二章 正则文法G=(V,T,P,S)1. 文法产生句子用到的是推导，判断一个句子的合法性可以使用产生语言文法的推导和规约进行判断2. 文法的构造。由给出的语言构造相应的文法，没有太直接的方法。常见的文法构造：L（G）= xn |n=1 G: Sx|xSL（G）= xn |n=0 G: SxS|L（G）= xn yn|n=1 G: SxSy|xyL（G）= xn yn|n=0 G: SxSy|重要结论：对于任意字母表，当要产生语言+时，只用在文法中对的每一个符号a安排如下形式的产生式就可以：Sa|As题目：设文法G的产生式集如下，试给出句子aaabbbccc的至少两个不同的推导和至少两个不同的归约SaBC|aSBCaBabbBbbCBBCbCbccCcc解：推导一： SaBC|aSBC aBab S=aSBC=aaSBCBC=aaaBCBCBC=aaabCBCBC=aaabBCCBC=aaabbCCBC=aaabbCBCC=aaabbBCCC=aaabbbCCC=aaabbbcCC=aaabbbccc 推导二： S=aSBC=aaSBCBC=aaaBCBCBC =aaaBBCCBC =aaaBBCBCC =aaabbCBCC=aaabbBCCC=aaabbbCCC=aaabbbcCC=aaabbbccc归约一、归约二分别为推导一和推导二的逆过程设，构造下列语言的文法。G: S aAB|aSABBAABaBabbBbbbAbaaAaaG: SaWa WaW|bW|cW|a|b|cG: G: 出现错误 第三章 有穷状态自动机1. 根据语言构造FA2. 根据NFA，构造与之等价的DFA(构造过程见P109)3. 根据文法构造相应的FA题目：x|x0，1+且当把x看成二进制时，x模5和3同余，要求当x为0时，|x|=1,且x0时，x的首字符为1 试构造相应的DFA1. 以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进入陷阱状态2. 设置7个状态：开始状态qs,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以5余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态qt3. 状态转移表为状态01q0q0q1q1q2q3q2q4q0q3q1q2q4q3q4x|x0，1*且如果x以1结尾，则它的长度为偶数；如果x以0结尾，则它的长度为奇数可将0，1*的字符串分为4个等价类。试分别构造相应的DFA和NFADFA构造:q0： e的等价类，对应的状态为终止状态q1:x的长度为奇且以0结尾的等价类q2：x的长度为奇且以1结尾的等价类q3: x的长度为偶且以0结尾的等价类q4: x的长度为偶且以1结尾的等价类NFA构造：根据给定的NFA，构造与之等价的DFA(略，详见前一位同学的题目)根据下列给定文法，构造相应的FA。 (1) 文法G1的产生式集合如下： G1: Sa|AaAa|Aa|cA|BbBa|b|c|aB|Bb|Cb(2) 文法G2的产生式集合如下： G2: Sa|Aa Aa|Aa|Ac|Bb Ba|b|c|Ba|Bb|Bc解答: 文法G1对应的FA如下所示文法G2对应的FA如下所示第四章 正则表达式1. 根据语言给出相应的正则表达式2根据正则表达式构造等价FA3. 根据DFA构造等价的正则表达式题目：判断题：r,s是字母表上的正则表达式r+e=r(rs)n=rnsnrs=sr以上都是错误的填空题语言的正则表达式是：语言的正则表达式是：写出表示下列语言的正则表达式。 xx0,1+ 且x的第10个字符是1 。解：所求正则表达式为：(0+1)91(0+1)*。 xx0,1*和如果x以1结尾，则它的长度为偶数；如果x以0结尾，则它的长度为奇数。解：所求正则表达式为：(0+1)2n+11+(0+1)2n0 (nN)或(0+1)(0+1)(0+1)*1+(0+1)(0+1)(0+1)(0+1)*0。 xx是十进制非负实数 。解：首先定义 .,0,1,2,3,4,5,6,7,8,9则所求正则表达式为：(0+1+9)*. (0+1+9)*。根据正则表达式构造FA和根据FA构造正则表达式略（参前一位同学）第五章 正则语言的性质就一题（参前一位同学）补：构造等价于下图所示DFA的正则表达式。Sq1q0q2q310001110答案(之一)：( 01+(1+00)(1+00*1)0)*(1+00*1)1) )* (e+(1+00)(1+00*1)0)*00*)q1q0q2q310001110eeXYe预处理：去掉q3：q1q0q21011+00*10eXYe00*去掉q1：q0q21+00(1+00*1)0eXYe00*(1+00*1)101q0eXYe+(1+00)(1+00*1)0)*00*01+(1+00)(1+00*1)0)*(1+00*1)1)去掉q2：去掉q0：XY(01+(1+00)(1+00*1)0)*(1+00*1)1)* (e+(1+00)(1+00*1)0)*00*)1、 设= a,b ,求字符串aaba的所有前缀、真前缀、后缀、真后缀。解： 前缀：a,aa,aab,aaba真前缀：，a,aa,aab后缀：，a,ba,aba,aaba真后缀：，a,ba,aba2、 设= 0,1 ,请给出上的下列语言的文法：(1) 所有含有3个连续0的串。解：S-A000AA-0A|1A|(2) 至少有3个0的串解：S-A0A0A0AA-0A|1A|3、 简单描述由下面的产生式对应的文法生成的语言。（1）S-Ab A-aAb A-解：L= anbn+1|n0 (2) S-aA A-bS S-解：L= （ab）n|n04、 构造识别下列语言的DFA.(1) L= x000|x 0,1 * (2)L= x|x 0,1 *且x中不含形如00的子串5、 构造识别下列语言的NFA(1) x|x 0,1 +,x能整除2 (2) 构造一个3个状态的NFA,接受的语言 ab,abc*6、 构造识别语言L(a+b)*b(a+bb)*)的NFA。7、 给出下图自动机接受的语言的正则表达式。去掉q1 去掉q2 去掉q0 所以该自动机接受的语言的正则表达式为：(ab