不确定性有限自动机

入门NFA

Posted by persuez on June 6, 2018

对比确定性有限自动机(DFA)

DFA:当给定了当前所在状态,在遇到一个字符之后,我们就可以确定要向哪一个状态转移。打个比方,就是在我们当前位置没有岔路口,没有给我们多选的机会。 NFA:NFA即不确定性有限自动机(nondeterminism finite automaton),它允许我们在遇到一个状态时可以有多条转移路径可以选择。特殊的是,它允许我们不读入任何字符就进行状态转移(此操作称为$\epsilon - move$)。 能力: 令人惊讶的是,DFA和NFA的能力相同。也就是说,DFA和NFA都只能识别正则语言。所以,现在一种语言是正则的当且仅当它可以被某个DFA或NFA识别。此结论在之后的文章中将会证明。

NFA的正式定义

NFA的正式定义和DFA差不多,但是因为NFA可以同时向多个状态转移,所以它的转移函数的值域应该是状态集$Q$的幂集(一个幂集是这个集合的所有子集的集合),记作$P(Q)$。除此之外,由于NFA还有$\epsilon - move$,所以它的转移函数应该是$Q \times \sum_\epsilon \to P(Q)$,其中$\sum_\epsilon = \sum \cup \lbrace \epsilon \rbrace$。因此我们可以继续用5元组$(Q, \sum, \delta, q_0, F)$定义NFA。

  1. $Q$是有限状态集。
  2. $\sum$是有限字符表。
  3. $\delta$是转移函数: $Q \times \sum_\epsilon \to P(Q)$。
  4. $q_0$是开始状态,它是$Q$中的元素。
  5. $F$是接受状态集合, 它是$Q$的子集。

例子

NFA样例图 对于$N_1=(Q, \sum, \delta, q_1, F)$,其中

  1. $Q=\lbrace\ q_1, q_2, q_3, q_4\rbrace$,
  2. $\sum=\lbrace\ 0, 1\rbrace$,
  3. $\delta$是: \(\begin{array}{c|ccc} & \text{0} & \text{1} & \epsilon \\ \hline q_1 & \lbrace q_1 \rbrace & \lbrace\ q_1, q_2 \rbrace & \emptyset \\ q_2 & \lbrace q_3 \rbrace & \emptyset & \lbrace q_3 \rbrace \\ q_3 & \emptyset & \lbrace q_4 \rbrace & \emptyset \\ q_4 & \lbrace q_4 \rbrace & \lbrace q_4 \rbrace & \emptyset, \end{array}\)
  4. $q_1$是开始状态,
  5. $F= \lbrace q_4 \rbrace$。

某个NFA $N$ accepts字符串$w$的定义

我们假定$N=(Q, \sum, \delta, q_0, F)$, $w = y_1y_2…y_m$,其中$y_i \in \sum_\epsilon$,如果存在一序列状态$r_0,r_1,…,r_m \in Q$使得以下3个条件成立,骂我们就说$N accepts w$:

  1. $r_0 = q_0$,
  2. $r_{i+1} \in \delta(r_i, y_{i+1}),其中i=0,…,m-1$,
  3. $r_m \in F$。

解释:上述第一个条件是指明NFA从开始状态出发;条件二表示当机器处于状态$r_i$时,它读到$w$中的字符时是可以转移到下一个状态的;条件三表明最后的转移状态$r_m$要属于接受集合。