（2）对于G中每一个形如A→a的产生式,将其变为S→Aa 12 (1)
状态矩阵是：
记[S]=q0 [B]=q1 [A B]=q2 [S A]=q3 ,最小化和确定化后如图
（2）记 [S]=q0, [A]=q1,[B S]=q2 最小化和确定化后的状态转换图如下
13 （1）将具有ε动作的NFA确定化后，其状态转换图如图：
记 { S0,S1,S3}=q0 {S1}=q1 {S2 S3}=q2 {S3}=q3
(2) 记{S}=q0 {Z}=q1 {U R}=q2 {S X}=q3 {Y U R}=q4 {X S U}=q5 {Y U R Z}=q6 {Z S}=q7
14（1）从略
(2)化简后S0和S1作为一个状态，S5和S6作为一个状态。
状态转换图如图
15从略。
16从略。
(1) r*表示的正规式集是{ε,r,rr,rrr,?}
(ε|r)*表示的正规式集是{ε, εε,?}∪{r,rr,rrr,?}={ε,r,rr,rrr,?}
ε|rr*表示的正规式集是{ε,r,rr,rrr,?}
(r*)*=r*={ε,r,rr,rrr,?}
所以四者是等价的。
(2)（rs）*r表示的正规式集是{ε,rs,rsrs,rsrsrs,?}r ={r,rsr,rsrsr,rsrsrsr,?}
r(sr)* 表示的正规式集是r{ε,sr,srsr,srsrsr,?} ={ r,rsr,rsrsr,rsrsrsr,?}
所以两者等价。
18 写成方程组
S=aT+aS(1)
B=cB+c(2)
T=bT+bB(3)
所以B=c*cT=b*bc*c
S=a*ab*bc*c G1:
S=aA+B(1)
B=cC+b(2)
A=abS+bB (3)
C=D(4)
D=bB+d(5)
把（4）（5）代入（2），得B＝c(bB+d)+b=cbB+cd+b 得B=(cb)*(cd|b),代入（3）得
A=abS+b(cb)*(cd|b)把它打入（1）得
S=a(abS+b(cb)*(cd|b))+ (cb)*(cd|b)
=aabS+ab(cb)*(cd|b) + (cb)*(cd|b)
=(aab)*( ab(cb)*(cd|b)| (cb)*(cd|b)) G2:
S=Aa+B (1)
A=Cc+Bb (2)
B=Bb+a(3)
C=D+Bab(4)
D=d(5)
可得 D=dB=ab*C=ab*ab|bA=(ab*ab|b)c + ab*b
S=(ab*ab|b)ca+ab*ba +ab*
=(ab*ab|b)ca| ab*ba| ab* 20
识别此语言的正规式是S=’LABEL’d(d|,d)*; 从略。 21 从略。
22 构造NFA
其余从略。
23 下面举一个能够识别1,2,3,10,20,100的例子，读者可以推而广之。 %{
#include
#include
#include
#define ON1
#define TW 2
#define THRE 3
#define TE 10
#define TWENT 20
#define HUNDRE 100
#define WHITE9999 %}
upper[A-Z] %%
ONEreturn ON;
TWOreturn TW;
THREEreturn THRE;
TENreturn TE;
TWENTYreturn TWENT;
HUNDREDreturn HUNDRE;
\
\\nreturn0; %%
main(int argc,char *argv[]) {
int c,i=0;
char tmp[30];
if (argc==2) {
if ((yyin=fopen(argv[1],\
{
printf(\ } }
while ((c=yylex())!=0) {
switch(c) {
case ON:
c=yylex();
if (c==0) goto {i+=1;label;}
c=yylex();
if (c==HUNDRE)
i+=100;
else i+=1;
break;
case TW:c=yylex();
c=yylex();
if (c==HUNDRE)
i+=200;
else i+=2;
break;