南开大学编译原理第三章课件演示幻灯.ppt

下载文档 降价啦

2
0
约2万字
约 194页
2018-02-28 发布于天津
举报
版权申诉
保障服务

南开大学编译原理第三章课件演示幻灯.ppt

1、本文档共194页，可阅读全部内容。
2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击这里二次下载。
4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。

NFA?DFA例1 0 8 5 4 7 3 6 2 1 e e e e e e e b a c e NFA?DFA例1（续） e -closure({0}) = { 0, 1, 2, 6, 8} e -closure(δ({ 0, 1, 2, 6, 8}, a) = e -closure({3}) = {3} e -closure(δ({ 0, 1, 2, 6, 8}, b) = e -closure({}) = {} e -closure(δ({ 0, 1, 2, 6, 8}, c) = e -closure({7}) = {1, 2, 5, 6, 7, 8} 0 8 5 4 7 3 6 2 1 e e e e e e e b a c e NFA?DFA例1（续） e -closure(δ({ 3}, a) = e -closure({}) = {} e -closure(δ({ 3}, b) = e -closure({4}) = {1, 2, 4, 5, 6, 8} e -closure(δ({ 3}, c) = e -closure({}) = {} 0 8 5 4 7 3 6 2 1 e e e e e e e b a c e NFA?DFA例1（续） e -closure(δ({ 1, 2, 5, 6, 7, 8}, a) = e -closure({3}) = {3} e -closure(δ({ 1, 2, 5, 6, 7, 8}, b) = e -closure({}) = {} e -closure(δ({ 1, 2, 5, 6, 7, 8}, c) = e -closure({7}) = {1, 2, 5, 6, 7, 8} 0 8 5 4 7 3 6 2 1 e e e e e e e b a c e NFA?DFA例1（续） e -closure(δ({ 1, 2, 4, 5, 6, 8}, a) = e -closure({3}) = {3} e -closure(δ({ 1, 2, 4, 5, 6, 8}, b) = e -closure({}) = {} e -closure(δ({ 1, 2, 4, 5, 6, 8}, c) = e -closure({7}) = {1, 2, 5, 6, 7, 8} 0 8 5 4 7 3 6 2 1 e e e e e e e b a c e NFA?DFA例1（续）哪些是终态 ? 1, 2, 5, 6, 7, 8 1, 2, 4, 5, 6, 8 0, 1, 2, 6, 8 3 c b a a a c c D C A B c b a a a c c 例3.15：(a | b)*abb NFA?DFA 0 1 2 3 5 4 6 7 8 9 10 e e e e e e e e a a b b b start 例3.15：（续）第一步： A = e -closure(0) = {0, 1, 2, 4, 7}作为DFA的初态 0 1 2 3 5 4 6 7 8 9 10 e e e e e e e e a a b b b start 例3.15：（续）第二步 a: e -closure(δ(A,a)) = e -closure(δ({0,1,2,4,7},a)) = e -closure({3,8}) = {1,2,3,4,6,7,8} = B Dtran[A,a] = B b : e -closure(δ(A,b)) = e -closure(δ({0,1,2,4,7},b)) = e -closure({5}) = {1,2,4,5,6,7} = C Dtran[A,b] = C 0 1 2 3 5 4 6 7 8 9 10 e e e e e e e e a a b b b start 例3.15：（续）第三步 a : e -closure(δ(B,a)) = e -closure(δ({1,2,3,4,6,7,8},a))} = {1,2,3,4,6,7,8} = B Dtran[B,a] = B b : e -closure(δ(B,b)) = e -closure(δ({1,2,3,4,6,7,8},b))} = {1,2,4,5,6,7,9} = D Dtran[B,b] = D e 0 1 2 3 5 4 6 7 8 9 10 e e e e e e e a a b b b start NFA例2 (a (b*c)) | (a (b | c+)?) 0 4 2 1 3 5 start c b e c b c e a 可接受abbc 例2的另一解法 3 2 b c a 1 6 5 7 c a c 4 b a (b*c) a (