woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

NFA到DFA的转换的算法

假设NFA N=(K, å,f,K0,Kt),则可按如下办法构造一个DFA  M=(S, å,d,S0,St),使得L(M)=L(N)

 

1.  M的状态集SK的一些子集组成。用[K1 K2... Kj]表示S的某一个元素,其中K1, K2,... KjK的状态。并且约定,状态K1, K2,... Kj是按无序的(无序集合),即对于子集{K1, K2}={ K2, K1}来说,S的状态就是[K1 K2]

 

2.  MN的输入字母表是相同的,即是å

 

3. 转换函数是这样定义的

 d([S1 S2,... Sj],a) = [R1R2... Rt]    其中     {R1,R2,... , Rt} =  e-closure(move({K1, K2,,... Kj},a))

 

4. S0=e-closure(K0)M的开始状态;

 

5. St={[Ki Kk... Ke],其中[Ki  Kk... Ke]ÎS{Si , Sk,,... Se}ÇKt¹F}

 

posted on 2009-11-27 14:36 肥仔 阅读(2123) 评论(0)  编辑 收藏 引用 所属分类: 状态机 & 自动机 & 形式语言


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理