发布时间 : 星期六 文章(整理完)编译原理网上作业题参考答案20121101更新完毕开始阅读
对于句子baba，画出二棵不同的语法树，因而是二义的。 11．有文法G[S]：S→iSeS|iS|i
该文法是否是二义的。试证明之。（﹡﹡） 解答：
对于句子iiiei，有两棵不同的语法树，故文法是二义的。
12．文法G[T]：T→aR，R→Tb|d生成的语言是什么？G[T]是否为3型文法？（﹡﹡） 解答：
不是3型文法。
13.试写出能够描述下列电话号码格式的文法。（﹡﹡）
67391742 010-67391742 (010)67391742
解答： 文法产生式规则如下： <电话号码> → <局代码> <本机码>
<电话号码> → <区前缀> <局代码> <本机码> <区前缀> → <地区码> ‘-’ <区前缀> → ‘(’ <地区码> ‘)’ <地区码> → DIG DIG <地区码> → DIG DIG DIG <局代码> → DIG DIG DIG DIG <本机码> → DIG DIG DIG DIG
14. 试构造生成语言的上下文无关文法。（﹡﹡﹡）
(1) { abc | n≥1,i≥0 }
(2) { w | w∈{a,b}，且w中a的个数恰好比b多1 }
解答：(1)把abc分成ab和c两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为：
nni
nn
i
+
nni
S → AB A → aAb|ab B → cB|ε
(2)令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下：
S → aE|Ea|bSS|SbS|SSb E → aEbE|bEaE|ε
15. 下面的二义性文法描述命题演算公式，为它写一个等价的非二义性文法。G[S]:S -> S AND S | S OR
S | NOT S | p | q | (S) （﹡﹡） 解答：G[S]:
S -> S AND A | A A -> A OR B | B B -> NOT B |p | q | (S)
16. 对于下列语言分别写出它们的正规表达式。 （﹡﹡）
(1) 英文字母组成的所有符号串，要求符号串中顺序包含五个元音。 (2) 英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。 解答：(1) 令Letter表示除这五个元音外的其它字母。
((letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter))* (2) A*B*....Z*
第三章 词法分析与有穷自动机
多项选择题：
1. ACE 2. ABD
填空题：
1．确定有限自动机DFA是（ NFA ）的一个特例。（﹡）
2．若二个正规式所表示的（ 正规集 ）相同，则认为二者是等价的。（﹡） 3．一个字集是正规的，当且仅当它可由（ DFA/NFA）所 （识别） 。（﹡）
判断题：
1． 错误 2．错误 3． 错误 4．正确 5．正确 6．正确 7．正确 8．正确 9．错误 10．正确
综合题：
1．设M＝（{x,y}, {a,b}, f,x,{y}）为一非确定的有限自动机，其中f定义如下： f（x,a）＝{x,y} f（a,b）＝{y} f（y,a）＝φ f（y,b）＝{x,y}
试构造相应的确定有限自动机M′。（﹡﹡）
解答：对照自动机的定义M=(S,Σ,f,S0,Z)， 由f的定义可知f(x,a)、f(y,b)均为多值函数，所以是一非确定有限自动机，先画出NFAM相应的状态图，如图下所示。
图 NFAM 用子集法构造状态转换矩阵下表所示。
将转换矩阵中的所有子集重新命名而形成下表所示的状态转换矩阵。
表状态转换矩阵
即得到M′＝（{0,1,2}, {a,b}, f,0, {1,2}），其状态转换图如下图所示。
由于{1,2}a={1,2}b={2}
{1,2}， 所以不再将其划分了，也即整个划分只有两组{0}，{1,2}：令状态1代
将上图的DFAM′ 最小化。首先，将M′的状态分成终态组{1，2}与非终态组{0}；其次，考察{1,2}。
表{1,2}，即把原来到达2的弧都导向1，并删除状态2。 最后，得到如下图所示化简DFAM′。
图 化简后的DFAM′
2．对给定正规式b*（d|ad）（b|ab）+，构造其NFAM。（﹡﹡）
解答：首先用A+=AA*改造正规式得：b*(d|ad)(b|ab)(b|ab)*； 其次，构造该正规式的NFAM，如下图所示。
图 NFAM
3．字母表{a，b}上的正规式R=（ba|a）*，构造R的相应DFA。（﹡﹡） 解答：
I x1y 1y 2 Ia 1y 1y 1y Ib 2 2