什么是非确定性有限自动机？

对于每个状态，都存在与相应字母表中的每个符号相对应的精确一个转移。这被称为确定性有限自动机 (DFA)。

非确定性有限自动机 (NFA)

对于每个状态，可以存在零个、一个、两个或多个与特定符号相对应的转移。

如果 NFA 进入一个状态，该状态存在多个与输入符号相对应的可能的转移，我们说它分支了。

如果 NFA 进入一个没有有效转移的状态，则该分支终止。如果存在某个转移选择会导致最终进入接受状态，则 NFA 接受输入字符串。

因此，一个接受分支足以使整体 NFA 接受，但所有分支都必须拒绝才能使整体 NFA 拒绝。

这是一个计算模型。我们编写 DFA 来指定确定性有限自动机。正式地，NFA 是一个 5 元组 (Q, ∑, q0 , T, δ)，与之前一样

  • Q 是有限的状态集
  • ∑ 是输入符号的字母表
  • q0 是起始状态
  • T 是 Q 的子集，给出接受状态
  • δ 是转移函数。
  • 现在，转移函数指定一组状态而不是一个状态：它将 Q☓ ∑ 映射到 {Q 的子集}。

示例 1

NFA 接受任何包含 00 或 11 作为子串的二进制字符串。如下所示：

示例 2

NFA 接受所有以 101 结尾的二进制字符串。如下所示：

更新于：2021年6月16日

1K+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告