资源描述：
《形式语言与自动机》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、形式语言与自动机（计算机网络班）第一章绪论1.幂集2.字母表的性质3.真前缀、真后缀、前缀、后缀4.语言的形式化表示题目：填空题{Φ,{Φ}}的幂集是：{Φ,{Φ},{{Φ}},{Φ,{Φ}}}判断题对于任何一个非空集合A,A2A错误{a,d,f}{a,b,c,…,z}是字母表正确ε一定是字符串的前缀或后缀，当字符串不为ε时，则ε一定是其真前缀或真后缀正确∑={aa,ab,bb,ba}，求字符串aaaaabbbba的所有前缀的集合、后缀的集合、真前缀的集合、真后缀的集合。解：由前缀、后缀、真前缀、真后缀的集合可以有：其前缀集合
2、为：{ε,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：。1)只有一对连续的1：。2)
3、没有连续的0并且没有连续的1：。3)有一对连续的0和一对连续的1：。所有长度为偶数的串。解答：所有倒数第10个字符是0的串。解答：{0,1}0{0,1}。第二章正则文法G=(V,T,P,S)1.文法产生句子用到的是推导，判断一个句子的合法性可以使用产生语言文法的推导和规约进行判断2.文法的构造。由给出的语言构造相应的文法，没有太直接的方法。常见的文法构造：L（G）={xn
4、n>=1}G:S→x
5、xSL（G）={xn
6、n>=0}G:S→xS
7、εL（G）={xnyn
8、n>=1}G:S→xSy
9、xyL（G）={xnyn
10、n>=0}G
11、:S→xSy
12、ε重要结论：对于任意字母表∑，当要产生语言∑+时，只用在文法中对∑的每一个符号a安排如下形式的产生式就可以：S→a
13、As题目：设文法G的产生式集如下，试给出句子aaabbbccc的至少两个不同的推导和至少两个不同的归约S→aBC
14、aSBCaB→abbB→bbCB→BCbC→bccC→cc解：推导一：S→aBC
15、aSBCaB→abS=>aSBC=>aaSBCBC=>aaaBCBCBC=>aaabCBCBC=>aaabBCCBC=>aaabbCCBC=>aaabbCBCC=>aaabbBCCC=>aaabbbCCC=
16、>aaabbbcCC=>aaabbbccc推导二：S=>aSBC=>aaSBCBC=>aaaBCBCBC=>aaaBBCCBC=>aaaBBCBCC=>aaabbCBCC=>aaabbBCCC=>aaabbbCCC=>aaabbbcCC=>aaabbbccc归约一、归约二分别为推导一和推导二的逆过程设，构造下列语言的文法。G:S→aAB
17、aSABBA→ABaB→abbB→bbbA→baaA→aaG:S→aWaW→aW
18、bW
19、cW
20、a
21、b
22、cG:G:出现错误第三章有穷状态自动机1.根据语言构造FA2.根据NFA，构造与之等价的D
23、FA(构造过程见P109)3.根据文法构造相应的FA题目：{x
24、xÎ{0，1}+且当把x看成二进制时，x模5和3同余，要求当x为0时，
25、x
26、=1,且x¹0时，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.状态转移表为状态01q0q0q1q1q2q3q2q4q0q3q1q2q4
27、q3q4{x
28、xÎ{0，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:S→a
29、AaA
30、→a
31、Aa
32、cA
33、BbB→a
34、b
35、c
36、aB
37、Bb
38、Cb(2)文法G2的产生式集合如下：G2:S→a
39、AaA→a
40、Aa
41、Ac
42、BbB→a
43、b
44、c
45、Ba
46、Bb
47、Bc解答:文法G1对应的FA如下所示文法G2对应的FA如下所示第四章正则表达式1.根据语言给出相应的正则表达式2．根据正
