内容发布更新时间 : 2024/4/25 8:20:42星期一 下面是文章的全部内容请认真阅读。
答案：
(1)串abbaa最左推导:
S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa 最右推导：
S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa (2)产生式有：S→ABS|Aa|εA→a B→SBB|b 可能元素有：εaa ab abbaa aaabbaa…… (3)该句子的短语有： a是相对A的短语 ε是相对S的短语 b是相对B的短语 εbb是相对B的短语 aa是相对S的短语
aεbbaa是相对S的短语 直接短语有：aεb 句柄是：a 第14题
给出生成下述语言的上下文无关文法： （1）{anbnambm|n，m>=0} （2）{1n0m 1m0n|n，m>=0}
（3）{WaWr|W属于{0|a}*，Wr表示W的逆} 答案： （１） S→AA A→aAb|ε （２） S→1S0|A A→0A1|ε （３）
S→0S0|1S1|ε 第16题
给出生成下述语言的三型文法： (1){an|n>=0}
(2){anbm|n,m>=1} (3){anbmck|n,m,k>=0} 答案： (1)S→aS|ε (2) S→aA A→aA|B B→bB|b (3)
A→aA|B
B→bB|C C→cC|ε 第17题
习题７和习题11中的文法等价吗？ 答案： 等价。 第18题
解释下列术语和概念： （１）字母表
（２）串、字和句子 （３）语言、语法和语义 答案：
（１）字母表：是一个非空有穷集合。 （２）串：符号的有穷序列。 字：字母表中的元素。
句子：如果Z x,x∈V*T则称x是文法G的一个句子。+
（３）语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所
有该语言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规 则构成的一切基本符号串组成的集合。
语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。
语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。 附加题
问题1：
给出下述文法所对应的正规式： S→0A|1B A→1S|1 B→0S|0 答案：
R=(01|10)(01|10)* 问题2：
已知文法G[A]，写出它定义的语言描述 G[A]:A→0B|1C B→1|1A|0BB C→0|0A|1CC 答案:
G[A]定义的语言由0、1符号串组成，串中0和1的个数相同. 问题3：
给出语言描述，构造文法.
构造一文法,其定义的语言是由算符+,*,(,)和运算对象a构成的算术表达式的集合. 答案一：
G[E]E→E+T|T T→T*F|F F→(E)|a 答案二：
G[E]E→E+E|E*E|(E)|a 问题4：
已知文法G[S]: S→dAB A→aA|a B→ε|bB
相应的正规式是什么？G[S]能否改写成为等价的正规文法？ 答案：
正规式是daa*b*；
相应的正规文法为(由自动机化简来)： G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b
也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε 问题5：
已知文法G： E→E+T|E-T|T T→T*F|T/F|F F→(E)|i
试给出下述表达式的推导及语法树 (1)i; (2)i*i+i (3)i+i*i (4)i+(i+i) 答案：
(1)E=>T=>F=>i
(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i (3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i
(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T) =>i+(i+T)=>i+(i+F)=>i+(i+i) (2) (3) (4) E+T i T F i F i E E+T E+T i T F
F (E) i T F i F
问题6：
已知文法G[E]: E→ET+|T T→TF*|F F→F^|a
试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄. 答案：
该句型对应的语法树如下： 该句型相对于E的短语有FF^^* 相对于T的短语有FF^^*,F 相对于F的短语有F^;F^^ 简单短语有F;F^ 句柄为F. 问题7：
适当变换文法，找到下列文法所定义语言的一个无二义的文法： S→SaS.SbS.ScS.d 答案：
该文法的形式很典型，可以先采用优先级联规则变换文法，然后再规定结合性对文法做 进一步变换，即可消除二义性。
设a、b和c的优先级别依次增高，根据优先级联规则将文法变换为： S→SaS.A A→AbA.C C→CcC.d
规定结合性为左结合，进一步将文法变换为： S→SaA.A A→AbC.C C→CcF.F F→d
该文法为非二义的。
问题8：
构造产生如下语言的上下文无关文法： （1）{anb2ncm|n，m≥0} （2）{anbmc2m|n，m≥0} （3）{ambn.m≥n}
（4）{a m b n c p d q.m+n=p+q} （5）{uawb.u,w∈{a,b}*∧|u|=|w|} 答案： （1）根据上下文无关文法的特点，要产生形如anb2ncm的串，可以分别产生形如anb2n和
形如cm的串。设计好的文法是否就是该语言的文法？严格地说，应该给出证明。但若不是
特别指明，通常可以忽略这一点。