形式系统

计算机专业教学
posts - 48, comments - 150, trackbacks - 0, articles - 10
  教师博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

如何理解NFA向DFA转换

Posted on 2006-04-30 00:35 形式系统 阅读(6647) 评论(8)  编辑 收藏 引用 网摘 所属分类: 编译原理

一个非确定自动机( NFA) 在读入符号串之后,并不确切地知道自动机处于哪个状态。但可以肯定一定处于状态集中的某一状态。该状态集记做 {q1,q2,…qk} 。而一个等价的确定自动机( DFA) 读入同样的 w 一定处于某个确定的状态上。这样,都是读入同样的 w DFA 到达某一个状态,而 NFA 到达某一个状态集。由 w 的任意性,可将 NFA 的所有的状态集和 DFA 的状态一一对应起来。这种对应的前提就是能识别同样的输入串。即 L(M1)=L(M2)

 

       显然,后一个状态集是依赖于前一个状态集的,是在前一个状态集的基础上,(其内任意结点)经过同一条路径到达的。下面是一个简单的例子:

   NFA to DFA_1.gif


可以看出,其核心是将 NFA 状态集归并为 DFA 中的状态。在 NFA 中,无论是从 1 4 ,还是 1 5 ,作为集合来讲都是集合 1 到集合 2 ,最为重要得是经过的条件都是 a 。因而从识别语言的效果是一样的。这使得这些弧合并成为可能。

考虑集合覆盖的情况。



 NFA to DFA_2.gif

一个结点属于第一个集合又同时属于第二个集合。这种情况不一定好理解。但如果从路径的历史的角度进一步区分,即不同的时间经过同一个结点,将其看成是不同的状态。按照这种时空的角度进一步区分,得到右图。这和图 1 是类似的。

 

再来看看带有终态结点的情况:

   NFA to DFA_3.gif


ab abb 均为该 NFA 识别的句子,其转换如下:

      

 

I a

Ib

A{1,2}

{3}

Φ

B{3}

Φ

{3,4}

C{3,4}

Φ

{3,4}

 

从某种意义上说。 NFA 中的状态 3 DFA 中被分离成两部分,当首次到达 3 时应该是状态 B ,而第二次以后再到达 3 则应该属于状态 C

根据规则, C{3,4} DFA 的终态,但在 NFA 中,只有 4 为终态, C 中仍然有 3 为非终态,若有路径 1 à 3 à 3 映射到 DFA 中也是 A à B à C ,何解?

  这里面最关键的是:对任意一个句子,总可以在两个图中分别找到一条路径,形成对应关系。并不是说 NFA 中的每条路径都要和 DFA 中的每条路径一一对应。

 

当识别句子 ab 时,选择由 3 直接到达 4 的路径。当识别句子 abb 时,则在状态 3 循环一次再到达 4

现在设想,通过 1 à 3 à 3 经过的路径也是 ab 。但此时并未到达终态。可以说,在到达 C 中的 3 时,必然选择了两个 b 以上的句子。

而这样的路径与选择句子有关系。

对于 NFA 能识别的句子,在 DFA 中也能识别。

对于 NFA 不能识别的句子,在 DFA 中也不能识别。

 

Feedback

# re: 如何理解NFA向DFA转换  回复  更多评论   

2006-06-30 00:46 by 谭楚荣
姚老师,关于那DFA的最小化我还是不怎么理解。。。。。。。。。

# re: 如何理解NFA向DFA转换  回复  更多评论   

2006-07-04 23:19 by 鲁超
不懂 你要多看看书嘛

# re: 如何理解NFA向DFA转换  回复  更多评论   

2006-07-08 17:38 by 形式系统
关于最小化看
http://www.teachblog.net/yhspace/archive/2006/07/07/1980.html

# re: 如何理解NFA向DFA转换  回复  更多评论   

2006-10-11 23:18 by 学生
谢谢老师!

# re: 如何理解NFA向DFA转换  回复  更多评论   

2007-08-24 17:44 by 123
不错不错 很通俗
先谢一下楼主 能找到这么通俗的说明很不容易!

# re: 如何理解NFA向DFA转换  回复  更多评论   

2007-12-13 04:04 by dfhdfh
http://what-is-in-fioricet-oral.lilli-jav.info
http://fioricet-pay-cod.lilli-jav.info
http://enorme-bite-gratuite.preteen-fou.info
http://baise-sexe-xxx.guardare-fou.info
http://les-grand-sexe-du-femme.moana-fou.info
http://blog-salope-exhib-urologie.persona-fou.info
http://sac-pique-nique.persona-fou.info
http://histoire-sexe-doberman.guardare-fou.info
http://fioricet-with-codeine-more-drug-side-effects.betty-jav.info
http://salope-uro.preteen-fou.info
http://blog-botte-cul.preteen-fou.info
http://petite-salope-naine.moana-fou.info
http://cul-sexe-gratuit.persona-fou.info
http://blonde-sexe-extrait-video.preteen-fou.info
http://beurette-video-sexe.guardare-fou.info
http://butalbital-fioricet-caffeine.lilli-jav.info
http://fioricet-2007-@yahoocom.lilli-jav.info
http://femme-re-sodomisa-e-sexe-gratuit.moana-fou.info
http://mature-plus-cul-defonce.guardare-fou.info
http://withdrawal-symptoms-fioricet.betty-jav.info
http://comment-savoir-si-une-chatte-est-enceinte.formato-fou.info
http://mature-clito.persona-fou.info
http://scene-cul-gratuite.preteen-fou.info
http://book-buy-cheap-fioricet-guest-info-site.betty-jav.info
http://extrait-sexe-gratuit-telecharger.guardare-fou.info
http://fioricet-specs.betty-jav.info

# re: 如何理解NFA向DFA转换  回复  更多评论   

2007-12-23 08:18 by scscsd
http://video-mature-free.teresa-tun.info
http://video-free-pornografico.teresa-tun.info
http://donna-matura-casalinga-amante-sesso-zona-bari.asiannudes-tun.info
http://sexe-payant-tel.gem-elb.info
http://video-de-film-de-cul.lexington-elb.info
http://figa-sesso-grosso-cazzo-gratis.teresa-tun.info
http://mature-gang-bang.asiannudes-tun.info
http://professoressa-scopano-ragazzo-voglioso.asiannudes-tun.info
http://photo-plus-gros-sexe-mondial.lexington-elb.info
http://exhibition-sexe-metz.denrico-elb.info
http://bonne-pute.lexington-elb.info
http://jeune-femme-chaleur-extrait-sexe.denrico-elb.info
http://sexe-blonde-gratuit.denrico-elb.info
http://touffe-rousse-sexe.vagine-elb.info
http://garce-net.gem-elb.info
http://cam-sexe-sur-msn.lexington-elb.info
http://pisciata-vaginali.asiannudes-tun.info
http://video-gratis-porno-teen.asiannudes-tun.info
http://code-bon-baiser-russie.lexington-elb.info
http://photo-sexe-arabe-gratuit.gem-elb.info
http://filmino-porno-sarzana.teresa-tun.info
http://jeune-garce-sodomise.gem-elb.info
http://video-grosse-chatte.lexington-elb.info

# re: 如何理解NFA向DFA转换  回复  更多评论   

2007-12-30 08:37 by dfhdfh
http://photo-sexe-bite.senegalese-ugx.info
http://fica-donna-nera.sculaccia-tun.info
http://chez-docteur-sexe-gynecologue.senegalese-ugx.info
http://giovani-pompinare-free.gradis-tun.info
http://film-cul-hardcore.culs-ugx.info
http://diciottenne-troia.gradis-tun.info
http://video-amateur-blog-cul.succhiano-ugx.info
http://minchie-foto.sculaccia-tun.info
http://slip-avec-gode-interne.succhiano-ugx.info
http://belong-to-you-eros-ramazzotti-video.gradis-tun.info
http://vieille-baise-minet.succhiano-ugx.info
http://signore-maggiorata-gratis.gradis-tun.info
http://site-rencontre-sexe-sans-payer.senegalese-ugx.info
http://sesso-ragazzo-15enni.sculaccia-tun.info
http://adulte-maghrebine-salope-photo.culs-ugx.info
http://foto-discoteca-xxx.sculaccia-tun.info
http://petite-puteavec-tout-petit-cul-tout-jeune.culs-ugx.info
http://video-amatoriale-scuola.fatte-tun.info
http://sexe-belle-fesse.senegalese-ugx.info
http://posizione-prima-volta-sesso.sculaccia-tun.info
http://dialogue-adulte-sexe.culs-ugx.info
http://250-galleria-transessuale.fatte-tun.info
http://sexe-star-porno.culs-ugx.info
http://vip-con-voglia-di-cazzo.fatte-tun.info
http://vieille-femme-qui-suce-grosse-bite-black.succhiano-ugx.info
http://annuncio-hard-gay.fatte-tun.info
http://groose-chatte.senegalese-ugx.info
http://racconto-gay-nero.gradis-tun.info
http://video-sexe-bretagne.culs-ugx.info

只有注册用户登录后才能发表评论。