目录
P36-6 (1)
P36-7 (1)
P36-8 (1)
P36-9 (2)
P36-10 (2)
P36-11 (2)
P64–7 (3)
P64–8 (4)
P64–12 (4)
P64–14 (6)
P81–1 (7)
P81–2 (8)
P81–3 (11)
P133–1 (11)
P133–2 (11)
P133–3 (13)
P134–5 (14)
P164–5 (18)
P164–7 (18)
P217–1 (18)
P217–3 (19)
P218–4 (19)
P218–5 (20)
P218–6 (21)
P218–7 (21)
P219–12 (21)
P270–9 (23)
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)
确定化：
最小化：
{,,,,,},{}
{,,,,,}{,,}{,,,,,}{,,,}
{,,,,},{},{}{,,,,}{,,}
{,,,},{},{},{}
{,,,}{,0123456012345135012345124601234560123413501234560123101
0==== 301231240123456011011223323401234561
01
01}{,,,}{,,}
{,},{,}{},{},{}
{,}{}{,}{,}
{,}{}{,}{}{},{},{,},{},{},{}
=====
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)
确定化：