第三章
N=>D=> {0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD
L={a |a(0|1|3..|9)n
且 n>=1}
(0|1|3..|9)n
且 n>=1
{ab,}
anbn
n>=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 1
<表达式><表达式><运算符><表达式>i+<表达式><运算符><表达式>i*
第9题 语法树
sss*ss+a
aa
推导: 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．
i2
短语：
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
3
00111010ε00014001020
(3)NFA
b (4)NFA
a2a0a1b42b0b1ε3εba5b6ε3εa,bab4
2.解：构造DFA矩阵表示 {X} {Z } {X,Z} {Y}
**00 {Z} {X,Z} {X,Z} {X,Y} 1 {X} {Y} {X,Y} 4
{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）解
构造状态转换矩阵：
5