第三章
N=>D=> {0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD
n
L={a |a(0|1|3、、|9) 且 n>=1}
n
(0|1|3、、|9) 且 n>=1 {ab,}
nn
abn>=1 第6题、
(1) <表达式> => <项> => <因子> => i
(2) <表达式> => <项> => <因子> => (<表达式>) => (<项>)
=> (<因子>)=>(i)
(3) <表达式> => <项> => <项>*<因子> => <因子>*<因子> =i*i
(4) <表达式> => <表达式> + <项> => <项>+<项> => <项>*<因子>+<项>
=> <因子>*<因子>+<项> => <因子>*<因子>+<因子> = i*i+i
(5) <表达式> => <表达式>+<项>=><项>+<项> => <因子>+<项>=i+<项> => i+<因子> => i+(<表达式>) => i+(<表达式>+<项>)
=> i+(<因子>+<因子>)
=> i+(i+i)
(6) <表达式> => <表达式>+<项> => <项>+<项> => <因子>+<项> => i+<项> => i+<项>*<因子> => i+<因子>*<因子> = i+i*i 第7题
<表达式><表达式><运算符><表达式><表达式><运算符><表达式>*ii+i<表达式><表达式><运算符><表达式>i+<表达式><运算符><表达式>i*i
第9题 语法树
sssasa+sa*
推导: S=>SS*=>SS+S*=>aa+a* 11、 推导:E=>E+T=>E+T*F 语法树:
EE+TT*F
短语: T*F E+T*F 直接短语: T*F 句柄: T*F
12．
短语：
13、(1)最左推导：S => ABS => aBS =>aSBBS => aBBS
=> abBS => abbS => abbAa => abbaa
最右推导：S => ABS => ABAa => ABaa => ASBBaa
=> ASBbaa => ASbbaa => Abbaa => a1b1b2a2a3
(2) 文法：S ? ABS
S ? Aa S ? ε A ? a
B ? b
(3) 短语：a1 , b1 , b2, a2 , , bb , aa , abbaa,
直接短语： a1 , b1 , b2, a2 , , 句柄：a1
14 (1)
S ? AB
A ? aAb | ε B ? aBb | ε (2)
S ? 1S0 S ? A
A ? 0A1 |ε
第四章
1. 1、 构造下列正规式相应得DFA (1) 1(0|1)*101
NFA
0111203140,1
(2) 1(1010*|1(010)*1)*0 NFA
00111010ε00014001020b
(3)NFA
2a0a1
b4a(4)NFA
ε3εa,b2b0b1ba5b6εε3ab4
2、解：构造DFA矩阵表示 0 1 {X}0 {Z} {X} {Z }* {X,Z} {Y} {X,Z} * {X,Z} {X,Y} {Y} {X,Y} {X,Y} {X,Y,Z} {X} {X,Y,Z} * {X,Y,Z} {X,Y} 其中0 表示初态，*表示终态
用0，1，2，3，4，5分别代替{X} {Z} {X,Z} {Y} {X,Y} {X,Y,Z} 得DFA状态图为：
11130000005012411
3．解：构造DFA矩阵表示 构造DFA得矩阵表示
0 1 {S}0 {V,Q} {Q,U} {V,Q} {Z,V} {Q,U} {Q,U} {V} {Q,U,Z} {Z,V}* {Z} {Z} {V} {Z} {Q,U,Z}* {V,Z} {Q,U,Z} {Z} {Z} {Z} 其中0 表示初态，*表示终态 替换后得矩阵 0 1 00 1 2 1 3 2 2 4 5 3* 6 6 4 6 5* 3 5 6 6 6 构造DFA状态转换图（略） 4．（1）解
构造状态转换矩阵： a b {0}0* {0,1} {1} {0,1}* {0,1} {1} {1} {0} 转换为 a b 0* 1 2 1* 1 2 2 0 {2，3} {0，1} {2，3}a={0,3} {2},{3},{0,1}
{0,1}a={1,1} {0,1}b={2,2} （2）解：首先把M得状态分为两组：终态组{0}，与非终态组{1，2，3，4,5} {1,2,3,4,5}a={1,3,0,5} {1,2,3,4,5}b={4,3,2,5}
由于{4}a={0} {1,2,3,5}a={1,3,5}
因此应将{1,2,3,4,5}划分为{4},{1,2,3,5} G=({0}{4}{1,2,3,5}) {1,2,3,5}a={1,3,5} {1,2,3,5}b={4,3,2}
因为{1,5}b={4} {23}b={2,3}
所以应将{1,2,3,5}划分为{1,5}{2,3} G=({0}{1,5}{2,3}{4})
此时G=( {0},{1,2,3,4,5} )
编译原理(清华大学 第2版)课后习题答案
