3m汽车膜授权店 常熟:帮忙解下编译原理题

1.构造正规式1(0|1)*101相应的DFA.

先构造NFA

确定化

0
1

X

A

A
A
AB

AB
AC
AB

AC
A
ABY

ABY
AC
AB

重新命名，令AB为B、AC为C、ABY为D

0
1

X

A

A
A
B

B
C
B

C
A
D

D
C
B

DFA：

2.将下图确定化：

0
1

S
VQ
QU

VQ
VZ
QU

QU
V
QUZ

VZ
Z
Z

V
Z

QUZ
VZ
QUZ

Z
Z
Z

重新命名，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。

0
1

S
A
B

A
C
B

B
D
E

C
F
F

D
F

E
C
E

F
F
F

DFA：

3.把下图最小化：

初始分划得∏0：终态组{0}，非终态组{1,2,3,4,5}

对非终态组进行审查：

{1,2,3,4,5}a {0,1,3,5}

而{0,1,3,5}既不属于{0}，也不属于{1,2,3,4,5}

∵{4} a {0}，所以得新分划

∏1：{0}，{4}，{1,2,3,5}

对{1,2,3,5}进行审查：

∵{1,5} b {4}

{2,3} b {1,2,3,5}，故得新分划

∏2：{0}，{4}，{1, 5}，{2,3}

{1, 5} a {1, 5}

{2,3} a {1,3}，故状态2和状态3不等价，得新分划

∏3：{0}，{2}，{3}，{4}，{1, 5}

这是最后分划了

最小DFA：

4.构造一个DFA，它接收∑={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正规式和正规文法。

按题意相应的正规表达式是0*(0 | 10)*0*或0*( 100*)*0*

构造相应的DFA，首先构造NFA为

用子集法确定化

I
I0
I1
S
0
1

{X,0,1,3,Y}

{0,1,3,Y}

{2}

{1,3,Y}
{0,1,3,Y}

{0,1,3,Y}

{1,3,Y}

{1,3,Y}
{2}

{2}

/

{2}
1

2

3

4
2

2

4

4
3

3

3

DFA：

可最小化，终态组为{1,2,4}，非终态组为{3}，{1,2,4}0 {1,2,4}，{1,2,4}1 {3}，所以1,2,4为等价状态，可合并。