##### 非确定型有限自动机 - 非确定型有限自动机 - **非确定型有限自动机** $\text{NFA}$ 是一种[[有限自动机]], 它扩展了[[确定型有限自动机]], 在状态转移上更加灵活, 每个状态对每个输入符号可能有零个, 一个或多个转移, 并且可以允许 $\varepsilon$ 转移, 即无需读取输入符号即可转移. 非确定性有限自动机可定义为一个五元组 $(Q, \Sigma, \delta, q_0, F)$ 满足以下条件 - $Q$ 是有限状态集合 - $\Sigma$ 有限输入字母表 - $\delta: Q \times \Sigma_{\varepsilon} \to \mathcal{P}(Q)$ 状态转移函数, $\mathcal{P}(Q)$ 是 $Q$ 的幂集, 意味着对于每个输入符号, 可以转移到一个或多个状态 - $q_0 \in Q$ 初始状态 - $F \subseteq Q$ 接受状态集合 >[!example]- 非确定型有限自动机 > ![[opentext_计算理论_2.png]] > - 状态图 > - 四个状态, 标记为 $q_1, q_2, q_3, q_4$ > - $q_1$, 初始状态, 循环读取 $0$ 或 $1$, 保持在 $q_1$, 但读取 $1$ 时可非确定性地转移到 $q_2$, 猜测这是倒数第三个符号 > - $q_2$, 表示已读取倒数第三个符号为 $1$, 等待下一个符号 > - $q_3$, 表示已读取倒数第二个符号, 等待最后一个符号 > - $q_4$, 接受状态, 表示倒数第三个符号为 $1$ 且已读取足够符号 > - 输入字母表, $\{0, 1\}$ > - 转移箭头, 从一个状态到另一个状态的箭头, 标记为 $0$ 或 $1$, 表示根据输入符号的转移规则 > - $\delta(q_1, 0) = \{ q_1 \}$ > - $\delta(q_1, 1) = \{ q_1, q_2 \}$ > - $\delta(q_2, 0) = \{ q_3 \}$, $\delta(q_2, 1) = \{ q_3 \}$ > - $\delta(q_3, 0) = \{ q_4 \}$, $\delta(q_3, 1) = \{ q_4 \}$ > - $\delta(q_4, 0) = \{ q_4 \}$, $\delta(q_4, 1) = \{ q_4 \}$ > - 计算过程 > - 接收输入字符串, 逐个读取符号, 从左到右处理, 并根据转移规则改变状态. 最终状态决定输出, 接受如果最后状态是接受状态, 拒绝如果最后状态不是接受状态. 输入字符串 $000100$ 最后接受 > - 接受语言 > - 所有字符串 $w = w_1 w_2 \cdots w_n$, 其中 $n \geq 3$, 满足倒数第三个符号 $w_{n-2} = 1$ > - $A = \{ w \in \{0, 1\}^* \mid |w| \geq 3 \text{且} w_{|w|-2} = 1 \}$