有哪些信誉好的足球投注网站- 1、本文档共18页，可阅读全部内容。
- 2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
查看更多
1.构造正规式的DFA。
（1）1(0|1)*101
首先构造NFA：
NFA化为DFA：
状态转换表：
Q 1 0 {X} A {ABC} B {ABC} B {BCD} C {BC} D {BCD} C {BCD} C {BCE} E {BC} D {BCD} C {BC} D {BCE} E {BCDY} Y {BC} D {BCDY} Y {BCD} C {BCE} E
状态转换图：
初态
1 0 A B B C D C C E D C D E Y D Y C E 化简后得：
（2）(a|b)*(aa|bb)(a|b)*
？
NFA化为DFA：
Q a b {X 1 2} {1 2 3} {1 2 4} {1 2 3} {1 2 3 5 Y} {1 2 4 } {1 2 4} {1 2 3} {1 2 4 5 Y} {1 2 3 5 Y} {1 2 3 5 Y} {1 2 4 Y} {1 2 4 5 Y} {1 2 3 Y} {1 2 4 5 Y} {1 2 4 Y} {1 2 3 Y} {1 2 4 5 Y} {1 2 3 Y} {1 2 3 5 Y} {1 2 4 Y}
所以，DFA为：
化简得：
（3）（0|11*0）*
NFA到DFA：
Q 1 0 {X A Y} X {B C D} A {A Y} B {B C D} A {C D} Y {A Y} B {A Y} B {B C D} A {A Y} B {C D} Y {C D} Y {A Y} B
化简后得；
2.将下图确定化和最小化。
a
a
? 0 1
a,b
解: 首先取A=ε-CLOSURE({0})={0}, NFA确定化后的状态矩阵为:
Q’ a b A {0} {0,1} {1} B {0,1} {0,1} {1} C {1} {0}
NFA确定化后的DFA为：
a
a
? A B
a
b b
C
将A,B 合并得:
a b
? A C
a
3.构造一个DFA，它接受∑={0，1}上所有满足如下条件的字符串，每个1都有0直接跟在后边。
解：按题意相应的正规表达式是0*(0 | 10)*0*
构造相应的DFA，首先构造NFA为
0 0 0
ε ε ε ε Y
1 0
用子集法确定化
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为
0
1 0 2
1 1 0
1
4
0
4.给出NFA等价的正规式R。
ε 1 1 ε 消去 得
0,1
ε 1 ε 消去其余结点
0，1
（0|1）*11
0|1）*11→右线性文法→正规式
A→0A|1A|1B
B→1C
C→ε
A=0A+1A+1B
B=1
A=0A+1A+11
A=(0+1)*11→(0|1)*11
5.试证明正规式（a|b）*与正规式（a*|b*）*是等价的。证明：
(1)
正规式(a|b)*的NFA为 = ε ε
b
a b {X, 1,y} {1,y} {1,y} {1,y} {1,y} {1,y}
a
其最简DFA为
文档评论（0）