如何在理论计算机科学（TOC）中将NFA转换为DFA？

在非确定性有限自动机中，对于任何当前状态和输入符号，都存在多个下一个输出状态。

当且仅当存在至少一条从初始状态开始并以最终状态结束的转换路径时，字符串才会被接受。

以下步骤用于将给定的 NFA 转换为 DFA：

算法

步骤 01

  • 让我们将“q”作为 DFA 的一组新状态。它最初被声明为空。
  • 让我们将 T’ 作为 DFA 的一个新的转换表。

步骤 02

  • 将 NFA 的起始状态添加到 q’ 中。
  • 从起始状态添加转换到 T’ 中。
  • 如果起始状态对于某些输入字母表具有到多个状态的转换，则在 DFA 中将这些多个状态作为单个状态接受。

步骤 03

如果 T’ 中存在任何新状态，

  • 将新状态添加到 q’ 中。
  • 在转换表 T’ 中添加状态的转换。

步骤 04

  • 继续重复第三步，直到转换表 T’ 中不再存在新状态。
  • 最后，获得的转换表 T’ 是所需 DFA 的完整转换表。

注意 -

转换后，DFA 中的状态数量可能与 NFA 中的状态数量相同，也可能不同。

DFA 中存在的最大状态数是 NFA 中状态数的两倍。

NFA 和 DFA 中的状态数 -

1 <= n <= 2m

这里，

  • n = DFA 中的状态数
  • m = NFA 中的状态数

在生成的 DFA 中，包含 NFA 的最终状态的所有状态都被视为最终状态。

更新于： 2021 年 6 月 12 日

2K+ 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告