DFA最小化--作业9

1.将DFA最小化：教材P65 第9题

I	{1,2,3,4,5}	{6,7}
	{3,4}b ->{6,7} {1,2}b ->{2} {5}b
II	{1,2} {3,4} {5}	{6,7}
	{1,2}a ->{3,4} {3,4}a {5}a ->{3,4}
III	{1,2} {3,4} {5}	{6,7}
	{1,2}c {3,4}c ->3 {5}c
IV	{1,2} {3,4} {5}	{6,7}
	{1,2}d {3,4}d ->{5} {5}d	{6,7}b ->{6}

 正规式：　b*a(c* | (ad)*) bb*

2.构造以下文法相应的最小的DFA

S→ 0A|1B

A→ 1S|1

B→0S|0

正规文法转换正规式：

　　S = 0A+0B

　　　= 0(1S+1)+1(0S+0)

　　　= 01S+01+10S+10

　　　= (01+10)S | (01+10)

　　　= (01 | 10)S | (01 | 10)

　　　= (01 | 10)* (01 | 10)

正规式转换自动机：

 转换成DFA:

		0	1
a	{AB}	C	D
b	C		{BE}
c	D	{BE}
d	{BE}	{CF}	{DH}
e	{CF}		{BEGI}
f	{DH}	{BEGI}
g	{BEGI}	{CF}	{DH}

 最小化DFA：

I	{a,b,c,d,e,f}	{g}
	{a}1 ->c {b}1 ->d {c,f}1  {d}1 ->f {e}1 ->g
II	{a}{b}{c,f}{d}{e}	{g}
	{c}0 ->d {f}0 ->g
III	{a}{b}{c}{d}{e}{f}	{g}

3.自上而下语法分析，回溯产生的原因是什么？

 答：因为文法的产生式有问题。

4.P100 练习4，反复提取公共左因子。

　　S -> C$

　　A -> aD | bAA

　　D -> ε | c

　　B -> bE | aBB

　　E -> ε c