精品文档
第二章
P36-6
(1)
L G ()1是0~9组成的数字串
(2)
最左推导:
N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒0010120127334
556568
最右推导:
N ND N ND N ND N D N ND N D N ND N ND N D ⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒77272712712701274434
886868568
P36-7
G(S)
O N O D N S O AO A AD N
→→→→→1357924680|||||||||||
P36-8
文法：
E T E T E T T
F T F T F F E i
→+-→→|||*|/()| 最左推导:
E E T T T
F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+********()*()*()*()*()*()*()
最右推导:
E E T E T
F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+⇒+**********()*()*()*()*()*()*()*()
语法树：/********************************
精品文档
E
E F
T
E +
T F F T +i
i
i
E
E
F
T
E
-T F F T -i
i
i
E
E
F
T
+T F F
T
i
i
i
*i+i+i
i-i-i
i+i*i
*****************/
P36-9
句子iiiei 有两个语法树：
S iSeS iSei iiSei iiiei S iS iiSeS iiSei iiiei ⇒⇒⇒⇒⇒⇒⇒⇒
P36-10
/**************
)
(|)(|S T T
TS S →→
***************/
P36-11
/*************** L1:
ε
||cC C ab aAb A AC S →→→ L2:
bc
bBc B aA A AB S ||→→→ε
L3:
ε
ε||aBb B aAb A AB S →→→ L4:
A
B B A A B A S |01|10|→→→ε ***************/
第三章习题参考答案
P64–7
(1)
101101(|)*
1 ε ε 1 0 1
1 确定化：
0 1 {X} φ {1,2,3} φ φ φ {1,2,3} {2,3} {2,3,4} {2,3} {2,3} {2,3,4} {2,3,4} {2,3,5} {2,3,4}
{2,3,5} {2,3} {2,3,4,Y} {2,3,4,Y}
{2,3,5}
{2,3,4,}
1 0
0 0 1 1 0
0 1 0 1 1 1 最小化：
X 1 2 3 4 Y
5 X
Y
6
0 1
2 3
5 4
{,,,,,},{}
{,,,,,}{,,}{,,,,,}{,,,}{,,,,},{},{}{,,,,}{,,}
{,,,},{},{},{}
{,,,}{,01234560123451350123451246012345601234135012345601231010
0==== 30123124012345601101122332340123456101
01}{,,,}{,,}
{,},{,}{},{},{}
{,}{}{,}{,}
{,}{}{,}{}{},{},{,},{},{},{}
===== 0
1
0 0 1 0
0 1 0 1 1 1
P64–8
(1)
01)0|1(*
(2)
)5|0(|)5|0()9|8|7|6|5|4|3|2|1|0)(9|8|7|6|5|4|3|2|1(*
(3)
******)110|0(01|)110|0(10
P64–12
(a)
a
a,b a
确定化：
a b {0} {0,1} {1} {0,1} {0,1} {1} {1}
{0}
φ
5 0
1 2 4 3 0
1
