发布时间 : 星期四 文章哈工大编译原理习题及答案更新完毕开始阅读
解：对应文法为 S→0A|1B|e，A→0S|1C B→0C|1S C→1A|0B 3.描述语言特点
（1）S→10S0S→aAA→bAA→a
解：本文法构成的语言集为：L(G)={(10)nabma0n|n, m≥0}。 （2）S→SS S→1A0A→1A0A→ε
解：L(G)={1n10n11n20n2 ? 1nm0nm |n1,n2,?,nm≥0；且n1,n2,?nm不全为零}该语言特点是：产生的句子中，0、1个数相同，并且若干相接的1后必然紧接数量相同连续的0。 （3）S→1AS→B0A→1AA→CB→B0B→CC→1C0C→ε
解：本文法构成的语言集为：L(G)={1p1n0n|p≥1,n≥0}∪{1n0n0q|q≥1,n≥0}，特点是具有1p1n0n 或1n0n0q形式，进一步，可知其具有形式1n0mn,m≥0,且n+m>0。 （4）S→bAdcA→AGSG→εA→a 解：可知，S=>?=>baSndc n≥0
该语言特点是：产生的句子中，是以ba开头dc结尾的串,且ba、dc个数相同。 （5）S→aSSS→a
解：L(G)={a(2n-1)|n≥1}可知：奇数个a
4.解：此文法产生的语言是：以终结符a1 、a2 ?an 为运算对象，以∧、∨、~为运算符，以[、]为分隔符的布尔表达式串
5. 5.1解：由于此文法包含以下规则：AA→e，所以此文法是0型文法。 5.2证明：略 6.解：
（1）最左推导：
<程序>T<分程序>T<标号>：<分程序>TL：<分程序> TL：<标号>：<分程序> T L：L：<分程序>
T L：L：<无标号分程序>
T L：L：<分程序首部>；<复合尾部>
T L：L：<分程序首部>；<说明>；<复合尾部> T L：L：begin<说明>；<说明>；<复合尾部> T L：L：begin d；<说明>；<复合尾部> T L：L：begin d；d；<复合尾部>
T L：L：begin d；d；<语句>；<复合尾部> T L：L：begin d；d；s；<复合尾部. T L：L：begin d；d；s；<语句> end T L：L：begin d；d；s；s end 最右推导：
<程序>T<分程序>T<标号>：<分程序> T<标号>：<标号>：<分程序> T<标号>：<标号>：<无标号分程序>
T<标号>：<标号>：<分程序首部>；<复合尾部>
T<标号>：<标号>：<分程序首部>；<语句>；<复合尾部> T<标号>：<标号>：<分程序首部>；<语句>；<语句>；end T<标号>：<标号>：<分程序首部>；<语句>；s；end T<标号>：<标号>：<分程序首部>；s；s；end T<标号>：<标号>：<分程序首部>；说明；s；s；end T<标号>：<标号>：<分程序首部>；d；s；s；end T<标号>：<标号>：begin 说明；d；s；s；end T<标号>：<标号>：begin d；d；s；s；end
T<标号>： L：begin d；d；s；s；end TL：L：begin d；d；s；s；end
（2）句子L：L：begin d；d；s；s end的相应语法树是：
7.解：
aacb是文法G[S]中的句子，相应语法树是：
最右推导：S=>aAcB=>aAcb=>aacb 最左推导：S=>aAcB=>aacB=>aacb
（2）aabacbadcd不是文法G[S]中的句子 因为文法中的句子不可能以非终结符d结尾 （3）aacbccb不是文法G[S]中的句子
可知，aacbccb仅是文法G[S]的一个句型的一部分，而不是一个句子。 （4）aacabcbcccaacdca不是文法G[S]中的句子
因为终结符d后必然要跟终结符a，所以不可能出现?dc?这样的句子。 （5）aacabcbcccaacbca不是文法G[S]中的句子
由（1）可知：aacb可归约为S，由文法的产生式规则可知，终结符c后不可能跟非终结符S，所以不可能出现?caacb?这样的句子。
8.证明：用归纳法于n，n=1时，结论显然成立。设n=k时，对于α1α2...αkT*b,存在βi：i=1,2,..,k，αiT*bi成立，现在设
α1α2... αkαk+1T*b，因文法是前后文无关的，所以α1α2... αk可推导出b的一个前缀b'，αk+1可推导出b的一个后缀=b\不妨称为b k+1)。由归纳假设，对于b'，存在βi ：i=1,2,..,k，b'=β1β2...βk,使得
αiT*bi成立，另外,我们有αk+1T*b\）。即n=k+1时亦成立。证毕。
9.证明：(1)用反证法。假设α首符号为终结符时，β的首符号为非终结符。即设：α=aω；β=Aω’且 α=>*β。
由题意可知：α=aωT ?T Aω’=β，由于文法是CFG，终结符a不可能被替换空串或非终结符，因此假设有误。得证；
（2）同（1），假设：β的首符号为非终结符时，α首符号为终结符。即设：α=aω；β=Aω’且α=aωT ?T Aω’=β，与（1）同理，得证。
10.证明：因为存在句子：abc，它对应有两个语法树（或最右推导）： STABTAbcTabc STDCTDcTabc