跳转至

非确定有穷自动机NFA

例：有0和1构成的串当中，接受全部以01结尾的串，如何设计有穷自动机？

  • DFA

img

  • 使用非确定有穷自动机

img

针对上述情形，有如下运转模式：

  • 开始处于\(q_0\)，如果读入1，则状态保持在\(q_0\)；
  • 读入0的话，处于两个状态，\(q_0\)和\(q_1\)；
  • 并且在\(q_1\)的时候，只有读入1，才可以跳转到\(q_2\)；
  • 即只有以01结尾，才可能跳转到状态\(q_2\) 。

同一状态在相同的输入下, 可以有多个转移状态，这样自动机在某一时刻可以处在多个状态
因此给定一个输入和当前状态，状态转移函数的输出是一个状态集

定义

定义：非确定有穷自动机(NFA, Non-deterministic Finite Automaton)A为五元组\(A=(Q,\Sigma,\delta,q_0,F)\)

  1. \(Q\): 有穷状态集；
  2. \(\Sigma\): 有穷输入符号集或字母表；
  3. \(\delta\): \(Q\times \Sigma\to2^Q\) 状态转移函数；
  4. \(q_0\subseteq Q\): 初始状态
  5. \(F\subseteq Q\): 终结状态集或接受状态集。

\(2^Q\)是幂集，即\(2^Q=\{S│S\subset Q\}\) (S是Q的子集)

\(\delta(q,a)=\{p_1,p_2,…,p_n\}\)

状态转移函数

扩展\(\delta\)到字符串，定义扩展转移函数为\(\hat{\delta}:Q\times \Sigma^*\to 2^Q\)为

\[\hat{\delta}(q,w)=\begin{cases}\{q\}&w=\epsilon\\\\\bigcup_{p\in\hat{\delta}(q,x)}\delta(p,a)&w=xa\end{cases}\]

上式中\(a\)是一个字符，\(w\)和\(x\)是字符串

当w不为空串的时候，先输入前面的字符串x，可以到达多个状态\(\hat{\delta}(q,x)\)。对每个状态应用状态转移函数，然后把状态求并集即可

DFA与NFA的等价性

定理：如果语言L被NFA接受，当且仅当L被DFA接受

从NFA到DFA：子集构造法

目标：从NFA： \(N=(Q_N,\Sigma,\delta_N,q_0,F_N)\)构造\(D=(Q_D,\Sigma,\delta_D,\{q_0\},F_D)\)，且\(L(D)=L(N)\)

  • 状态集：\(Q_D=2^{Q_N}\)，即每个状态是\(Q_N\)的子集
  • 接受状态集：\(F_D=\{S|S\subset Q_N,S\cap F_N=\Phi\}\)
  • 状态转移函数：\(\forall S\subset Q_N,\forall a\in \Sigma,\delta_D(S,a)=\bigcup_{p\in S}\delta_N(p,a)\)

比如某个DFA的某个状态\(\{q_1,q_2,q_3\}\)，输入符号a，那么\(\delta_D(\{q_1,q_2,q_3\},a)\)是\(\delta_N(q_i,a)的并集\)

例：请将下面“接受全部以 01 结尾的串”的NFA转化成等价的DFA。

img

0 1
\(\to q_0\) \(\{q_0,q_1\}\) \(\{q_0\}\)
\(q_1\) \(\Phi\) \(\{q_2\}\)
\(*q_2\) \(\Phi\) \(\Phi\)

1.列出DFA所有可能的状态集（NFA状态集的所有子集）

0 1
\(\Phi\) \(\Phi\) \(\Phi\)
\(\to\{q_0\}\) \(\{q_0,q_1\}\) \(\{q_0\}\)
\(\{q_1\}\) \(\Phi\) \(\{q_2\}\)
\(\{q_2\}\) \(\Phi\) \(\Phi\)
\(\{q_0,q_1\}\) \(\{q_0,q_1\}\) \(\{q_0,q_2\}\)
\(\{q_0,q_2\}\) \(\{q_0,q_1\}\) \(\{q_0\}\)
\(\{q_1,q_2\}\) \(\Phi\) \(\{q_2\}\)
\(\{q_0,q_1,q_2\}\) \(\{q_0,q_1\}\) \(\{q_0,q_2\}\)

2.转移状态为NFA相应状态的并集

3.删除不能从开始状态到达的状态（无用状态）

0 1
\(\to\{q_0\}\) \(\{q_0,q_1\}\) \(\{q_0\}\)
\(\{q_0,q_1\}\) \(\{q_0,q_1\}\) \(\{q_0,q_2\}\)
\(\{q_0,q_2\}\) \(\{q_0,q_1\}\) \(\{q_0\}\)

4.含有NFA接受状态的状态集就是DFA的接受状态

0 1
\(\to\{q_0\}\) \(\{q_0,q_1\}\) \(\{q_0\}\)
\(\{q_0,q_1\}\) \(\{q_0,q_1\}\) \(\{q_0,q_2\}\)
\(*\{q_0,q_2\}\) \(\{q_0,q_1\}\) \(\{q_0\}\)

img