Nfa和dfa等价性证明

NFA和DFA等价转换

Posted by persuez on June 7, 2018

每个NFA都有一个等价的DFA

证明思路(NFA转DFA的方法)

我们要证明NFA和DFA等价,因为DFA是NFA的一般化,所以NFA一定可以模拟DFA,因此我们需要做的是用DFA模拟NFA。因为NFA在当前状态读到一个字符后可以有多条路可以走,所以模拟该NFA的DFA将有$2^k$个状态,每个状态都是NFA状态集的幂集的一个元素。具体操作在证明过程中。

证明

假设我们有一台NFA $N=(Q, \sum, \delta, q_0, F)$识别语言$A$,现在我们要构造一台DFA $M=(Q^{'}, \sum, \delta^{'}, q_0^{'}, F^{'})$识别语言$A$。在完整构造$M$之前,我们先假设$N$没有$\epsilon-move$。之后再考虑$epsilon-move$的情况。

  1. $Q^{'}=P(Q)$,这个条件是理解这个构造的关键,如果理解了1和下面的3,那基本整个构造就理解了。如果不能理解,那可以先放下,先看后面具体的例子。
  2. 注意$M$和$N$中的字符表是一样的。
  3. $\delta^{‘}(R, a)=\lbrace\ q \in Q \mid\ q \in \delta(r, a),\ r \in R\ \rbrace$,其中$R \in Q^{'}$。我们知道,$R$是$M$的一个状态,它也是$N$的一些状态的集合。当$M$在状态$R$遇到字符$a$时,那么我们要记录$N$中处于集合$R$中的所有元素时,$N$向哪个状态转移。所以上述转移函数也可以写为\(\delta^{'}(R, a)=\bigcup_{r \in R}\delta(r, a)\)
  4. $q_0^{‘}={q_0}$。
  5. $F^{‘}=\lbrace\ R \in Q^{‘} \mid \ R包含N的一个接受状态 \rbrace$。这个条件表示如果$N$有一条路走到接受状态,那么$M$就接受该字符串。

现在我们开始考虑$\epsilon-move$: 想法依旧是上述想法:模拟(stimulate)。但是为了方面表示,我们需要引入额外的记号。对于$M$的一个状态$R$,我们记$E(R)$为$R$的元素通过$\epsilon-move$可以到达的状态和$R$本身的并集。也就是\(E(R)=\lbrace\ q \mid q是可以从R出发通过0或0次以上\epsilon-move到达的状态\ \rbrace\)。有了这个定义,我们修改转移函数为:\(\delta^{'}(R, a)=\lbrace\ q \in Q \mid\ q \in E(\delta(r, a)),\ r \in R\ \rbrace\)。另外我们还需要修改开始状态为:$q_0^{‘}=E({q_0})$。至此,$N$的等价DFA$M$构造成功。撒花~

推论

一个语言是正则的当且仅当有某个NFA可以识别它。

NFA转DFA例子

NFA转DFA样例图 由图可知,$N_2$有3个状态,所以要构造的等价DFA$D$的状态集为$\lbrace \emptyset, \lbrace\ 1\ \rbrace, \lbrace\ 2\ \rbrace, \lbrace\ 3\ \rbrace, \lbrace\ 1, 2\ \rbrace, \lbrace\ 1, 3\ \rbrace, \lbrace\ 2, 3\ \rbrace, \lbrace\ 1, 2, 3\ \rbrace \rbrace$。确定了状态集之后,接下来我们要确定开始状态和接受状态集合。因为$N_4$的开始状态为1,所以$D$的开始状态为$E(\lbrace\ 1\ \rbrace)$,又有一个$\epsilon-move$由状态1到状态3,所以$E(\lbrace\ 1\ \rbrace)=\lbrace\ 1, 3\ \rbrace$。又$N_2$的接受集合只有一个元素1,所以$N_2$的状态集的幂集中包含1的集合都是$D$的接受状态,由此,$D$的接受集合为$\lbrace\ \lbrace\ 1\ \rbrace, \lbrace\ 1, 2\ \rbrace, \lbrace\ 1, 3\ \rbrace, \lbrace\ 1, 2, 3\ \rbrace$。最后我们确定转移函数(因为字符表是一样的,因此不需要理会),在这里,我们只分析几个状态的转移,其他的是一样的照葫芦画瓢。在$D$中:

  1. 状态$\lbrace\ 2\ \rbrace$: 状态$\lbrace\ 2\ \rbrace$读到字符a向状态$\lbrace\ 2, 3\ \rbrace$转移,这是因为在$N_2$中,状态2读到字符a向状态2或3转移,并且状态2或3都没有箭头从$\epsilon$出发;状态$\lbrace\ 2\ \rbrace$读到字符b向状态$\lbrace\ 3\ \rbrace$转移,这是因为在$N_2$中,状态2读到字符b只能向状态3转移,并且状态3没有箭头从$\epsilon$出发。
  2. 状态$\lbrace\ 1\ \rbrace$: 状态$\lbrace\ 1\ \rbrace$读到字符a后向状态$\emptyset$转移,这是因为在$N_2$中,状态1没有箭头读到字符a后向其他状态转移;状态$\lbrace\ 1\ \rbrace$读到字符b后向状态$\lbrace\ 2\ \rbrace$转移,相信到此原因已经不用解释了。
  3. 状态$\lbrace\ 3\ \rbrace$: 状态$\lbrace\ 3\ \rbrace$读到字符a后向$\lbrace\ 1, 3\ \rbrace$转移,这是因为在$N_2$中,状态3在读到字符a后向状态1转移,并且在状态1有一个$\epsilon$箭头从状态1指向状态3;状态$\lbrace\ 3\ \rbrace$读到字符b后向$\emptyset$转移。
  4. 状态$\lbrace\ 1, 2\ \rbrace$: 状态$\lbrace\ 1, 2\ \rbrace$读到字符a后向状态$\lbrace\ 2, 3\ \rbrace$转移,这是因为在$N_2$中,状态1读到字符a后,没有转移的状态,状态2读到a后向状态2或3转移,并且没有额外的$\epsilon$转移;状态$\lbrace\ 1, 2\ \rbrace$读到字符b后向状态$\lbrace\ 2, 3\ \rbrace$转移,此处原因不再过多解释。继续模拟其余4个状态(总共$2^3=8$个状态),将得到以下DFA: 和$N_2$等价的DFA图

但是上图并不是最简的DFA图,我们可以入度为0的节点(在DFA图中,节点即是状态,入度为0即没有箭头指向该节点)去掉,因为不可能有节点去到那个节点(开始节点入度至少为1),所以这类节点是对DFA没有贡献的。在上图中,状态$\lbrace\ 1\ \rbrace$和状态$\lbrace\ 1, 2\ \rbrace$均属于没有贡献的状态,所以可以去掉它们,得到下图: 和$N_2$等价的DFA图

下篇文章将用NFA证明正则操作(并,连接,闭包)的封闭性。