资源描述：
《10学习指导与习题解答-9》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第九章语言和有限状态机§9.1基本要求1.掌握语法结构、语言、演绎、演绎树的概念，能识别语法结构的分类，能写岀一个语法的Backus-Naurfornrio2.掌握带有输出的有限状态机的定义，能够使用状态图和状态表表示带有输出的有限状态机。3.会求串联、kleene闭包，掌握没有输出的有限状态机（有限状态自动机）的概念，了解非确定的有限状态机，知道能被一个非确定的有限状态口动机是别的语言也可以被一个确定的有限状态自动机识别。4.学握正则表达式和正则集合的概念，了解KLEENE定理。知道一个集合是由一个正则语法产生的当且仅当它是
2、正则集合。了解其他种类的有限状态机。5.掌握Turing机的概念，知道Turing机如何识别一个符号串。§9.2主要解题方法9.2.1语法结构与语言的关系1.使用语法中所有的可能使用的产生式，将从S演绎出來的符号串求出來，或者将这样的符号串的规律找出來。这样就求出了一个语法所产生的语言。例9.2.1设G是一个语法结构，字母表为V二{S,A,a,b},终止符集合T={a,b},初始符号为S,产生式P二{S-aA,S-*b,A-aa},这个语法的语言L(G)是什么？解：用产生式S->aA可以从初始状态S演绎出aA,用产生式S-b可
3、以演绎出b,用产生式A->aa从aA可以演绎出aaa,没有任何其它的词可以被演绎出來了，所以L(G)={b,aaa}□例9.2.2设G是一个语法结构，字母表为V={S,0,1},终止符集合T二{0,1},初始符号为S,产生式P二{S-11S,S-0},这个语法的语言L(G)是什么？解：用产生式S-0可以从初始状态S演绎出0,用产生式S-11S可以演绎出11S,从11S可以演绎出110或者1111S,从1111S可以演绎出11110和llllllSo在演绎的过程屮，我们或者在S前加两个1,或者把S替换成0而结束演绎。所以L(G)
4、={0,110,11110,1111110,・・・},这个集合中的符号串都是以偶数个1开头，然后由一个0结束。2.给出一个语言，可以根据此语言的规律构造产生这个语言的语法结构。同一个语言可以有多个语法结构來产生。例9.2.3给出一个语法结构，可以产生集合{0niln
5、m和n是非负整数}。解：我们将给出两个产生这个集合的语法GpG2,这说明两个不同的语法可以产生同一个语言。语法G
6、的字母表是V二{S,0,1},终止符集合T={0,1),产生式为S-OS,S-S1,和S—入。这个语法就能产生我们要求的集合，因为用第一个产生式m次就
7、可以把m个()放在串的前面，用第二个产生式n次就可以把n个1放在串的后面。语法G2的字母表是V二{S,A,0,1},终止符集合T={0,1),产生式为S-OS,S-1A,S-1,A-1A,A-H和S-入。这个语法也能产生我们要求的集合。9.2.2根据语法结构产生式的特点来判断语法结构的类型根据下血的表格就可以判断语法结构的类型。语法的类型类型对于产生式的限制W]fW20没有任何限制1W]的长度小于等于W2长度，或者W2=n2Wi=A,A是非终止符。3S~X,或者W］二A并且W2=aB或者W2=a,其中A,B是非终止符。例924
8、设语法是6=(V,T,S,P),其中，V={0,1,S,A},T={0,1},S是初始符，产生式为S-0S1A；S-入；A-1A；llA-Oo则这个语法是0型语法。例9.2.5设语法是G二(V,T,S,P),其中V二{0,1,2,S,A,B},T={0,1,2},初始状态是S,产生式是S-OSAB,S->入，BA-AB,0A->01,1A-11,1B-12,2B-22o则这个语法是上下文有关的语法(1型语法)。例926设语法是G二(V,T,S,P),其中，V={0,1,S},T={0,1},S是初始符,产生式为S-0S1；S-
9、*Xo则这个语法是上下文无关的语法(2型语法)。例927设语法是G二(V,T,S,P),其中，V二{S,A,0,1},终止符集合T={0,1},产生式为S-OS,S-1A,S-1,A-1A,A-1和S-入。则这个语法是正则语法(3型语法)。9.2.3求演绎树以及判断一个词是否属于一个语法产生的语言一个由上下文无关语法产生语言的演绎可以用一个有序的根树來表示，一个这样的演绎就対应一个有跟树。例9.2.8给出书中例子中关于ahungrymathematicianeatswildly的演绎的演绎树。nounphrasearticle
10、adjectivenounverbphrasehungrymathematicianeats判断一个符号串是否在一个由上下文无关语法产生的语言中，我们有两种解决办法。第一种方法是自顶向下分析，从s开始，试图使用一系列的产生式来演绎出要判断的词；第二种方法称为自底向上的分析，在
