第三章
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,}
a n
b n 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题
第9题
语法树
s
s s* s s+a
a a
推导: S=>SS*=>SS+S*=>aa+a*
11. 推导:E=>E+T=>E+T*F
语法树:
E
+T
*
短语: 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
(2) 1(1010*|1(010)*1)*0
NFA
(3)NFA
(4)NFA
b
其中0 表示初态，*表示终态
用0，1，2，3，4，5分别代替{X} {Z} {X,Z} {Y} {X,Y} {X,Y,Z} 得DFA状态图为：
3．解：构造DFA矩阵表示
构造DFA的矩阵表示
其中表示初态，*表示终态
替换后的矩阵
4．（1）解
构造状态转换矩阵：
{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} 此时G=( {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})
{1,5}a={1,5} {1,5}b={4} 所以{1,5} 不用再划分
{2,3}a={1,3} {2,3}b={3,2}
因为 {2}a={1} {3}a={3} 所以{2,3}应划分为{2}{3}
所以化简后为G＝（ {0},{2},{3},{4},{1,5}）
7.去除多余产生式后，构造NFA如下
确定化，构造DFA 矩阵
G={(0,1,3,4,6),(2,5)} {0,1,3,4,6}a={1,3}
{0,1,3,4,6}b={2,3,4,5,6}
所以将{0,1,3,4,6}划分为 {0,4,6}{1,3} G={(0,4,6),(1,3),(2,5)}
{0,4,6}b={3,6,4} 所以 划分为{0},{4,6} G={(0),(4,6),(1,3),(2,5)}
不能再划分，分别用 0，4，1，2代表各状态，构造DFA 状态转换图如下；
b
8．代入得
S = 0(1S|1)| 1(0S|0) = 01(S|ε) | 10(S|ε) = (01|10)(S|ε)
= (01|10)S | (01|10)
