（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;