twzheng's cppblog

『站在风口浪尖紧握住鼠标旋转！』 http://www.cnblogs.com/twzheng
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  136 随笔 :: 78 文章 :: 353 评论 :: 0 Trackbacks
不确定的有穷自动机N的确定化
[源] http://www2.gdin.edu.cn/jkx/webstudy/bianyiyuanli/fornpage/chapter03/section3/03.3.3.htm

不确定的有穷自动机N的确定化
　　根据定义，显然DFA是NFA的特例。对于每个NFA M，存在一个DFA M′，使得 L(M)=L(M′)。
　　对于任何两个有穷自动机M和M′，如果L(M)=L(M′)，则称M与M′是等价的。
　　我们将介绍一种算法，对于给定的NFA M，构造其等价的DFA M′。
　　请你注意这个结论：DFA是NFA的特例
　　对每个NFA N一定存在一个DFA M，使得L(M)=L(N)。对每个NFA N存在着与之等价的DFA M。与某一NFA等价的DFA不唯一。
　　在有穷自动机的理论里，有这样的定理：设L为一个由不确定的有穷自动机接受的集合，则存在一个接受L的确定的有穷自动机。我们不对定理进行证明，只介绍一种算法（这种算法称为子集法），将NFA转换成接受同样的语言的DFA。
　　为什麽对DFA如此亲睐呢？因为它的行为很容易用程序来模拟。
　　DFA M=（K，Σ，f，S，Z）的行为的模拟程序
程序段 　　　K:=S；
　　　c:=getchar;
　　　while c<>eof do
　　　　{K:=f(K,c);
　　　　　c:=getchar;
　　　　};
　　　if K is in Z then return (‘yes’)
　　　　else return (‘no’)
　　从NFA的矩阵表示中可以看出，表项通常是一个状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本想法是该DFA的每一个状态对应NFA的一组状态。该DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态。也就是说，在读入输入符号串a1a2…an之后，该DFA处在这样一个状态，该状态表示这个NFA的状态的一个子集T，T是从NFA的开始状态沿着某个标记为a1a2…an的路径可以到达的那些状态。
　　为介绍算法首先定义对状态集合I的几个有关运算：
　　1. 状态集合I的ε-闭包，表示为ε-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条ε弧而能到达的状态的集合。
　　回顾在前面章节对转换函数的扩充：如输入字符是空串，则自动机仍停留在原来的状态上，显然，状态集合I的任何状态S都属于ε-closure(I)。
　　2. 状态集合I的a弧转换，表示为move(I,a)，定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。
　　我们使用图4.4的NFA N的状态集合来理解上述两个运算。
图 4.4 NFA N
　　ε-closure(0)=｛0，1，2，4，7｝
　　即｛0，1，2，4，7｝中的任一状态都是从状态0经任意条ε弧可到达的状态，令｛0，1，2，4，7｝=A，则 move(A,a)=｛3，8｝，因为在状态0，1，2，4和7中，只有状态2和7有a弧射出，分别到达状态3和8。
　　而ε-closure(｛3，8｝)=｛1，2，3，4，6，7，8｝。

　　再看一个例子，对下图所示NFA的状态集合I的运算
图 4.5
　　I={1},ε-closure(I)={1,2}；
　　I={5},ε-closure(I)={5,6,2}；
　　move({1,2},a)={5,3,4}
　　ε-closure({5,3,4})={2,3,4,5,6,7,8}；

　　NFA确定化算法：假设NFA N=(K, ∑,f,K0,Kt)按如下办法构造一个DFA M=(S, ∑,d,S0,St)，使得L(M)=L(N)：
　　① M的状态集S由K的一些子集组成（k的子集构造算法见下页）。用[S1 S2... Sj]表示S的元素，其中S1, S2,,... Sj是K的状态。并且约定，状态S1, S2,,... Sj是按某种规则排列的，即对于子集{S1, S2}={ S2, S1,}来说，S的状态就是[S1 S2]；
　　② M和N的输入字母表是相同的，即是∑；
　　③ 转换函数是这样定义的：
　　d([S1 S2,... Sj],a)= [R1R2... Rt] 其中 {R1,R2,... , Rt} = e-closure(move({S1, S2,,... Sj},a))
　　④ S0=e-closure(K0)为M的开始状态；
　　⑤ St={[Si Sk... Se]，其中[Si Sk... Se]∈S且{Si , Sk,,... Se}∩Kt≠φ}

构造NFA N的状态K的子集的算法：
　　假定所构造的子集族为C，即C= (T1, T2,,... TI),其中T1, T2,,... TI为状态K的子集。
① 开始，令e-closure(K0)为C中唯一成员，并且它是未被标记的。
② while （C中存在尚未被标记的子集T）do {
　　标记T；
　　for 每个输入字母a do
　　{
　　　U:= e-closure(move(T,a))；
　　　　if U不在C中 then
　　　　将U作为未标记的子集加在C中
　　}
　}
例题 例 3.3 应用左面的算法对图4.4的NFA N构造子集，步骤如下：
  　　① 首先计算ε-closure(0)，令T0=ε-closure(0)={0，1，2，4，7}，T0未被标记，它现在是子集族C的唯一成员。
　　② 标记T0；令T1=ε-closure(move(T0,a))={1，2，3，4，6，7，8}，将T1加入C中，T1未被标记。
　　令T2=ε-closure(move (T,b))={1，2，4，5，6，7}，将T2加入C中，它未被标记。
　　③ 标记T1；计算ε-closure(move(T1,a))，结果为{1，2，3，4，6，7，8}，即T1，T1已在C中。
　　计算ε-closure(move(T1,b))，结果为{1，2，4，5，6，7，9}，令其为T3，T3加至C中，它未被标记。
　　④ 标记T2，计算ε-closure(move(T2,a))，结果为{1，2，3，4，6，7，8}，即T1，T1已在C中。
　　计算ε-closure(move(T2,b))，结果为{1，2，4，5，6，7}，即T2，T2已在C中。
　　⑤ 标记T3，计算ε-closure(move(T3,a))，结果为{1，2，3，4，6，7，8}，即T1。
　　计算ε-closure(move(T3,b))，结果为{1，2，4，5，6，7，10}，令其为T4，加入C中，T4未被标记。
　　⑦ 标记T4，计算ε-closure(move(T4,a))，结果为{1，2，3，4，6，7，8}，即T1
　　计算ε-closure(move(T4,b))结果为{1，2，4，5，6，7}，即T2。
　　至此，算法终止共构造了五个子集：
　　T0={0，1，2，4，7} T1={1，2，3，4，6，7，8}
　　T2={1，2，4，5，6，7} T3={1，2，4，5，6，7，9}
　　T4={1，2，4，5，6，7，10}
　　那么图4.4的NFA N构造的DFA M为
　　① S={[T0]，[T1]，[T2]，[T3]，[T4]}
　　② Σ={a,b}
　　③ D([T0]，a)=[T1] D([T2]，a)=[T1]
　　　 D([T0]，b)=[T2] D([T2]，b)=[T2]
　　　 D([T1]，a)=[T1] D([T3]，a)=[T1]
　　　 D([T1]，b)=[T3] D([T3]，b)=[T4]
　　　 D([T4],a)=[T1]
　　　 D([T4]，b)=[T2]
　　④ S0=[T0]
　　⑤ St=[T4]
　　不妨将[T0]，[T1]，[T2]，[T3]，[T4]重新命名，以利于书写，或用A，B，C，D，E或用0，1，2，3，4分别表示。若采用后者，该DFA M的状态转换图如图4.6所示。
图 4.6 DFA M
 
又例：将下图的NFA确定化
划分子集及重新命名：
Ia Ib
{i,1,2} S {1,2,3} A {1,2,4} B
{1,2,3} A {1,2,3,5,6,f} C {1,2,4} B
{1,2,4} B {1,2,3} A {1,2,4,5,6,f} D
{1,2,3,5,6,f} C {1,2,3,5,6,f} C {1,2,4,6,f} E
{1,2,4,5,6,f} D {1,2,3,6,f} F {1,2,4,5,6,f} D
{1,2,4,6,f} E {1,2,3,6,f} F {1,2,4,5,6,f} D
{1,2,3,6,f} F {1,2,3,5,6,f} C {1,2,4,6,f} E
确定化后的自动机：
posted on 2007-04-03 22:20 谭文政 阅读(1814) 评论(1)  编辑 收藏 引用 所属分类: 基础知识

评论

# re: 不确定的有穷自动机N的确定化 2011-05-12 09:44 归地方
图片失效鸟  回复  更多评论
  


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