NFA与DFA

计算理论是计算机科学的一个分支，研究如何用算法解决问题。它有三个分支，即：；计算复杂性理论、可计算性理论和自动机理论。

自动机或自动机理论是研究可以用来解决计算问题的抽象数学机器或系统。自动机由状态和转换组成，当它看到输入的符号或字母时，它将当前状态和符号作为输入，转换到另一个状态。

自动机或自动机理论有几个类，包括确定性有限自动机（DFA）和不确定性有限自动机（NFA）。这两类是自动机或自动机的转移函数。

在转换过程中，DFA不能使用n个空字符串，它可以理解为一台机器。如果字符串以不可接受的状态结束，DFA将拒绝它。DFA机器可以用每一个输入和输出来构造。

对于字母表的每个符号，DFA只有一个状态转换，对于它的转换只有一个最终状态，这意味着对于每个被读取的字符，DFA中有一个对应的状态。在DFA中检查成员身份比较容易，但构造起来比较困难。在DFA中允许回溯，它比NFA需要更多的空间。

NFA中并不总是允许回溯。虽然在某些情况下是可能的，但在另一些情况下则不然。它更容易构造NFA，并且需要更少的空间，但是不可能为每个输入和输出构造NFA机器。

它被理解为同时计算的几台微型机器，成员身份可能更难检查。它使用空字符串转换，每对状态和输入符号都有许多可能的下一个状态。它从一个特定的状态开始读取符号，然后自动机根据当前的输入和其他后续事件来确定下一个状态。在接受状态下，NFA接受字符串，否则拒绝它。

总结：

1.“DFA”代表“确定性有限自动机”，而“NFA”代表“不确定性有限自动机”。2.两者都是自动机的转移函数。在DFA中，下一个可能的状态是明确设置的，而在NFA中，每对状态和输入符号可以有许多可能的下一个状态。3.NFA可以使用空字符串转换，而DFA不能使用空字符串转换。4.NFA更容易构造，而构造DFA则更难。5.在DFA中允许回溯，而在NFA中可能或可能回溯不允许。6.DFA需要更多的空间，而NFA需要更少的空间。7.虽然可以将DFA理解为一台机器，并且可以为每个输入和输出构造一台DFA机器，但是8.可以将NFA理解为多台同时计算的小型机器，并且不可能为每个输入和输出构造一台NFA机器。