如何构造一个接受所有以0开头的二进制字符串的NFA？

Question

只是想要一些关于如何构建以 0 开头的 MFA 的帮助或提示

Answer 1

以零 (0) 开头的所有二进制字符串 (Alphabet = {0, 1}) 的非确定性有限自动机 (NFA) 可以构造如下。

首先，我们知道 NFA 需要一个初始状态。所有 NFA 都需要一个初始状态。将此称为 q0。

当我们最初进入状态q0时，我们还没有看到所需的0；空字符串不以 0 开头。因此，初始状态 q0 不接受。到目前为止，我们的 NFA 还没有接受状态。这意味着它还不接受任何东西。不过，我们的语言中包含字符串，因此我们知道任何 NFA 必须不仅仅具有初始的、非接受状态 q0。调用我们知道需要 q1 的另一个状态。

我们引入了 q1 因为我们需要一个接受状态。从q0开始，如果我们看到符号0，我们就看到了目标语言中的一个字符串（实际上是最短的字符串）。从符号 0 上的 q0 开始的转换必须终止于某种接受状态。我们不妨终止于 q1；因此，我们添加转换 f(q0, 0) = q1。

我们的 DFA 现在接受由长度为 1 的字符串 0 组成的有限语言； L(M) = {0}。到目前为止，我们不接受任何其他内容。然而，我们想要接受的语言包括更长的字符串。因此，我们的 NFA 中需要更多的东西。我们知道，到目前为止我们添加的内容在逻辑上是强制性的，并且该语言的任何正确的 NFA 本质上都会执行我们迄今为止所做的操作（模空、epsilon 或 lambda 转换，这些转换是不必要的）。

特别是，我们希望接受更多以 0 开头的字符串。所有以 0 开头的字符串都将采用我们添加的从 q0 到 q1 的转换。因此，在状态 q1 中，我们基本上需要接受从该点开始看到的任何内容。如果接下来看到 0，我们需要进入接受状态；如果我们接下来看到 1，我们需要进入接受状态 - 等等，永远。因为此时我们不需要区分任何类型的字符串，所以我们可以简单地在 0 或 1 上添加从 q1 回到自身的转换。

到目前为止，我们的 NFA 看起来有点像这样：

               +----+
               |    | 0, 1
               V    |
----->q0----->q1----+
          0

您应该能够说服自己此 NFA 接受预期语言，因为：

• 它接受的最短字符串是0
• 如果它接受字符串 x，则它接受字符串 x0 和 x1
• 所有以0开头的字符串都可以使用上述规则构造
• 使用上述规则不能构造出不以 0 开头的字符串

Answer 2

L={以“0”开头的字符串集} ={0,00,01,000,001,010,011,...}

首先，我们从初始状态（q0）开始。然后，如果我们得到“0”作为输入，它应该定向到最终状态（q1，因为我们检查“0”是第一个）。这里我们不关心如果输入为“1”会发生什么。因为这里我们设计的是NFA而不是DFA。在获得“0”作为第一个输入后，稍后可以有“0”/“1”输入。因此，我们将它们表示为 q1 状态。 NFA 对于上述问题