下载文档原格式
第2章形式语言基础2.2 设有文法G[N]: N -> D | NDD -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9(1)G[N]定义的语言是什么?(2)给出句子0123和268的最左推导和最右推导。
解答：(1)L(G[N])={(0|1|2|3|4|5|6|7|8|9)+} 或L(G[N])={α| α为可带前导0的正整数}(2)0123的最左推导：N ⇒ ND ⇒ NDD ⇒ NDDD ⇒ DDDD ⇒ 0DDD ⇒ 01DD ⇒ 012D ⇒ 0123 0123的最右推导：N ⇒ ND ⇒ N3 ⇒ ND3 ⇒ N23 ⇒ ND23 ⇒ N123 ⇒ D123 ⇒ 0123268的最左推导：N ⇒ ND ⇒ NDD ⇒ DDD ⇒ 2DDD ⇒ 26D ⇒ 268268的最右推导：N ⇒ ND ⇒ N8 ⇒ ND8 ⇒ N68 ⇒ D68 ⇒ 2682.4 写一个文法，使其语言是奇数的集合，且每个奇数不以0开头。
解答：首先分析题意，本题是希望构造一个文法，由它产生的句子是奇数，并且不以0开头，也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾。
如果数字只有一位，则1、3、5、7、9就满足要求，如果有多位，则要求第1位不能是0，而中间有多少位，每位是什么数字（必须是数字）则没什么要求，因此，我们可以把这个文法分3部分来完成。
分别用3个非终结符来产生句子的第1位、中间部分和最后一位。
引入几个非终结符，其中，一个用作产生句子的开头，可以是1－9之间的数，不包括0，一个用来产生句子的结尾，为奇数，另一个则用来产生以非0整数开头后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。
N -> 1 | 3 | 5 | 7 | 9 | BNB -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | B02.7 下面文法生成的语言是什么？G1：S->ABA->aA| εB->bc|bBc G2：S->aA|a A->aS解答：B ⇒ bcB ⇒ bBc⇒ bbccB ⇒ bBc⇒ bbBcc ⇒ bbbccc……A ⇒εA ⇒ aA ⇒ aA ⇒ aA ⇒ aaA ⇒ aa……∴S ⇒ AB ⇒ a m b n c n , 其中m≥0,n≥1即L(G1)={ a m b n c n | m≥0,n≥1} S ⇒ aS ⇒ aA ⇒ aaS ⇒ aaaS ⇒ aA ⇒ aaS ⇒ aaaA ⇒aaaaS ⇒ aaaaa ……∴S ⇒ a2n+1 , 其中n≥0即L(G2)={ a2n+1 | n≥0}2.11 已知文法G[S]: S->(AS)|(b)A->(SaA)|(a)请找出符号串(a)和(A((SaA)(b)))的短语、简单短语和句柄。
形式语言与自动机课后作业答案第二章4．找出右线性文法，能构成长度为1 至5 个字符且以字母为首的字符串。
答：G={N,T,P,S}其中N={S,A,B,C,D} T={x,y} 其中x € {所有字母} y € {所有的字符} P 如下:S T x S T xA A f y A f yBB T y B T yC C T y C T yD D T y6．构造上下文无关文法能够产生L={ 3 / {a,b}*且3中a的个数是b的两倍}答：G={N,T,P,S}其中N={S} T={a,b} P 如下:S t aab S t aba S t baaS t aabS S t aaSb S t aSab S t SaabS t abaS S t abSa S t aSba S t SabaS t baaS S t baSa S t bSaa S t Sbaa7．找出由下列各组生成式产生的语言(起始符为S)(1) S t SaS S t b(2) S t aS b S t c(3) S T a S f aE aS答：(1) b(ab)n /n > 0}或者L二{(ba)n b/n > 0}(2) L={a n cb n /n > 0}(3) L={a2n+1 /n > 0}第三章1. 下列集合是否为正则集，若是正则集写出其正则式。
（1）含有偶数个a和奇数个b的{a,b}*上的字符串集合（2）含有相同个数a和b的字符串集合（3）不含子串aba的{a,b}*上的字符串集合答：（1）是正则集，自动机如下b b b b⑵不是正则集，用泵浦引理可以证明，具体见17题（2）（3）是正则集先看L '为包含子串aba的{a,b}*上的字符串集合显然这是正则集，可以写出表达式和画出自动机。
（略）则不包含子串aba的{a,b}*上的字符串集合L是L '勺非根据正则集的性质，L 也是正则集。
4 题：文法G 的产生式集合如下，试给出句子aaabbbccc 的一个推导和一个归约S T aBCIaSBCCB T BCaB t abbB t bbbB t bbC t bccC t ccC t cc6 题：文法G 的产生式集合如下，请给出G 中每个语法范畴代表的集合S t aSaIaaSaaIaAaA t bAIbbbAIbBB t cBIcCC t ccCIDDD t dDId7 题: 给定如下文法，请用自然语言描述它们定义的语言(4)S t aBIbAA t aIaSIBAAB t bIbSIABB8题：设刀={0,1},请给出刀上下列语言的文法(3)所有以11 开头, 以11 结尾的串;(6)所有长度为偶数的串9题：设刀={a,b,c},构造下列语言的文法(2)L2={ a n b m|n,m》1}(3)L3={ a n b n a n|n》1}(4)L4={a n b m a k|n,m,k > 1}(6)L6={xwx T| x,w +}(7)L?={w | w = w T, w +}补充：对给定RGS t abAIbaBA t abAIabB t baBIba构造等价文法，新文法的产生式形如：A T a, A T aB, A,B € V , a€ T参考答案4、文法G的产生式集合如下，试给出句子S T aBC|aSBCCB T BCaB T abbB T bbbB T bbC T becC T eeC T ee答：S 二aSBC=aaSBCBC=aaaBCBCBC=aaabCBCBC=aaabBCCBC=aaabbCCBC=aaabbCBCC=aaabbBCCC=aaabbbCCC=aaabbbeeC=aaabbbeee6、文法G的产生式集合如下，请给出S T aSa|aaSaa|aAaA T bA|bbbA|bBB TC B|C CC T CC C|DDD T dD|d解：(注意方法)Set(D)= {d m| m> 1} set(C)= {e 2n d m| n> 0,m > 2}(注意：aaabbbeee的一个推导和一个归约G中每个语法范畴代表的集合d只要大于n mset(B)= {e d | n> 1,m> 2}set(A)= {b k e n d m| k> 1,n》1,m>2}set(S)= {a p b k e n d m a p| p> 1,k > 1, n> 1,m > 2} 问题：2,不一定是偶数，可以没有e)不可写作：S={……}讨论：*n nS= a Aa*n i m f n=a b Ba*二a n b m e x Ca n*n ■ m x_ —=a b e DDa5 a n b m e x d y a nn - m x - y nS ={a b e d a | n,m, x -1,y -2} 06级张言飞7（4）、给定如下文法，请用自然语言描述它们定义的语言S T aB|bAA T a|aS|BAAB t b|bS|ABB解：该文法定义字母表刀={a,b}上的所有a和b的个数相等的字符串构成的语言。
语言学2章测试题及答案一、选择题（每题2分，共20分）1. 语言学的主要研究对象是什么？A. 语言的起源B. 语言的结构C. 语言的演变D. 语言的使用答案：B2. 下列哪项不是语言学的分支学科？A. 语音学B. 语法学C. 心理学D. 语义学答案：C3. 索绪尔认为语言符号是由哪两部分组成的？A. 语音和语义B. 符号和意义C. 能指和所指D. 形式和内容答案：C4. 语言的最小意义单位是什么？A. 音素B. 词C. 语素D. 句子5. 语言的交际功能不包括以下哪一项？A. 信息传递B. 情感表达C. 思维工具D. 艺术创作答案：C6. 语言的规范性主要体现在哪个方面？A. 发音B. 语法C. 词汇D. 所有选项答案：D7. 语言的多样性主要体现在哪些方面？A. 语言结构B. 语言使用C. 语言发展D. 所有选项答案：D8. 语言的演变不包括以下哪一项？A. 语音变化B. 词汇变化C. 语法变化D. 语言消亡答案：D9. 以下哪种现象不属于语言接触？B. 融合C. 分化D. 同化答案：C10. 语言的标准化通常不涉及以下哪一项？A. 发音规范B. 词汇规范C. 语法规范D. 语言的起源答案：D二、填空题（每题2分，共20分）1. 语言学研究的两个主要对象是______和______。
答案：语言；言语2. 索绪尔将语言符号分为______和______。
答案：能指；所指3. 语言的三个基本功能包括______、______和______。
答案：表达功能；交际功能；思维功能4. 语音学研究的是______和______。
答案：语音的产生；语音的感知5. 语用学研究的是______和______。
答案：语境；意义6. 语言的演变包括______、______和______。
答案：语音变化；词汇变化；语法变化7. 语言的接触现象包括______、______和______。
答案：借用；融合；同化8. 语言的多样性表现在______、______和______。
第二章形式语言与文法练习题
姓名：学号： 1101070211 班级：2班
一、单选题
1.给定文法：A→bA|cc,下面的符号串为该文法句子的是（）。
① cc ② bcbcc ③ bccbcc ④ bbbcc
A. ①④
B. ①②③
C. ①③
D. ②③④
2.文法G[Z]和语言L（G[Z ]）存在如下关系（）。
A.一一对应：一个文法对应唯一的语言；并且反过来，一个语言对应唯一的文法。
B.一个语言对应唯一的文法，反之则不然。
C.一个文法对应唯一的语言，反之则不然。
D.若G为非二义性文法，则C是正确的；若G为二义性文法，则一个文法不对应唯一的语言。
3. 有文法G[E]：E→－EE，E→－E，E →a|b|c 则文法的句子－－a－bc的所有可能的语法树有（）棵。
A. 1
B. 2
C. 4
D. 3
4.有文法G[S]，如果S x，( x∈V T )，则x是（）。
A. 句型
B. 句子
C. A和B
D. 非A和非B
二.构造一个上下文无关文法G，使得：L(G)={ a2m b m|m>0}
三.已知文法G[E]：E→ET+ | T
T→TF* | F
F→FP↑| P
P→(E) | i
有句型TF*PP↑+，问此句型的短语，
简单短语和句柄是什么？（画语法树说明）。
