将初始状态下任何输入字符缺少转换的 NFA 转换为 DFA

Question

我正在练习 NFA（非确定性有限自动机）设计并将它们转换为 DFA。

然后我突然有了一个疑问，因为我见过的所有转换示例都具有 NFA 的初始状态以及所有转换，即针对每个输入字符。

表格转换方法需要将初始状态放入表格中，这也成为DFA的初始状态。

但是，当初始状态下的每个输入字符没有出现所有转换时怎么办？考虑下面的例子......

示例： 如果我们想为 1^n0^m 创建 NFA，其中 n 和 m 都大于零。

所以我为 NFA 创建了这样的东西：

现在如果我们为此制作一个转换表...... 会是这样的：

由于我们在推导 DFA 转换表时考虑了初始状态：

但是从 NDFA 的表 q0 没有为输入 0 定义转换。在这种情况下应该如何进行......？

我陷入困境，因为初始状态本身并不完整。

另外，我在设计 NFA 时真的很困惑，因为 NFA 不是确定性的，所以除了语言字符串之外的任何混乱也可以被接受。在设计 DFA 时，可以通过消除或接受过程来删除状态和转换。

**通过在这里发布这个问题，我不希望得到这个具体问题的答案。 ** 在设计 NFA 并将其转换为 DFA 时，我正在寻找任何特定的规则集，以及极端情况，例如上面的情况。根据我的理解，我专门寻找 NFA，而不是可以进行空移动的 epsilon-NFA。

任何参考或深入研究材料将不胜感激。

Answer 1

因此，在浏览了一些与 NFA 到 DFA 转换相关的类似问题并选择了有关它们的详细信息之后。我有了更好的理解。

由于这些问题都不是根据我的理解量身定制的，所以我在这里给出了我因为发布这些问题而得到的答案。

第一个问题是“设计 NFA 是否有一套特定的规则？”。答案是否定的，除了我们拥有的极少数基本规则之外，没有具体的方法可以实现。只要我们的目标不是实现最小 NFA，就可能有无限个 NFA 接受相同的语言，并且显然具有冗余状态和转换。

“但是从 NDFA 的表 q0 没有为输入 0 定义转换。在这种情况下应该如何进行......？”如果出现任何此类情况，则意味着 DFA 将过渡到死亡状态。 （我详细了解了如何在 Q 的幂集中找到一个状态，从而找到 DFA）。

这是任何遇到同样困惑的人的解决方案（不知道是否有帮助，但无论如何）

NFA 的 δ

所以程序是这样的。

1. 首先写下初始状态转换：
   

2. 如果对于任何特定输入，从初始状态到输入 1 上的 {q0,q1}，存在到多个状态的集体转换，那么该状态集合应被视为单个状态，并且将成为外交部。
   DFA 的 δ 建筑
   

3. 为了扩展或定义 {q0, q1} 的转换，我们需要找到 {Q} 的幂集中的所有状态，这些状态在来自此 {q0, q1} 的每个输入字符上转换，其中 Q 是 NFA 状态的集合。
   最简单的方法是从 NFA 的 delta 中获取 {q0, q1} 状态的转换并集。
   因此，对于输入 0，突出显示的 q0 导致 ⲫ，q1 导致 {q1, q2}，它们的并集将是 {q1, q2}。
   

   因此，在 DFA 中，对于输入 0，{q0, q1} 将导致 {q1, q2}。
   DFA 的 δ 建筑
   

   以同样的方式，对于输入 1，q0 导致 {q0, q1} 并且 q1 导致 到 ⲫ，它们的并集将是 {q0, q1}。
   

   这样我们的DFA就可以完成了...
   DFA 的 δ 建筑
   

4. 最后我们只需要继续扩展任何新引入的 以类似的方式进行状态，直到所有状态都处于转换状态 表已展开。
   因此，对于我们当前的 DFA {q1, q2} 状态尚未定义：

   DFA 的 δ 建筑
   

   让我们完成这个。
   对于 NFA Delta 中的输入 0
   q1->{q1, q}
   q2-> q2
   并集 = {q1, q2}

   

   对于 NFA 中的输入 1
   q-1-> ⲫ
   q2->ⲫ
   联合 = {ⲫ]

   

   既然不再有任何集体国家 展开，这就是我们最终的DFA。

   这是相同的图表：

   

PS：我不是画家。