过渡中的歧义：如何在NFA中处理字符串？

Question

我已经根据给定的正则表达式制作了DFA，以匹配测试字符串。在某些情况下.*会发生这种情况。（例如.*ab）。假设现在计算机处于状态1。在DFA中，.*是指所有字符到其自身的过渡， 是指从状态1到a的另一过渡。如果测试字符串包含“ a”，则可能是过渡，因为从状态1开始，计算机可以进入两种状态，这在DFA中是不可能的。

Answer 1

^{我从您的示例开始，以便使您发现它对您有帮助。}
任何一类自动机都可以有两种形式：

• 确定性
• 非确定性的。

在确定性模型中：我们只有一个选择（或者说没有选择）才能从一个祝贺转移到下一个配置。
在有限自动（DFA）的确定性模型中：对于状态（Q）和语言符号（？）的每种可能组合，我们始终具有唯一的下一个状态。

DFA转换函数的定义：？：Q×？？问

?(q0, a) ? q1
            ^ only single choice

因此，在DFA中，从一个状态到下一个状态的所有可能移动都是确定的。

而
在非确定性模型中：对于下一个配置，我们可以有多个选择。
而在有限自动机（NFA）的非deterministaic模式：输出设定状态的一些国家（Q）和语言符号的组合（？）。

NFA转换函数的定义：？：Q×？？2 ^Q =？问

?(q0, a) ? {q1, q2, q3}
               ^ is set, Not single state (more than one choice)

在NFA中，对于下一个状态，我们可以有多个选择。也就是说，您将过渡NFA称为歧义。

（您的示例）
假设语言符号为? = {a, b}，语言/正则表达式为(a + b)*ab。您使用的这种语言的有限自动机可能类似于以下内容：

您的问题是： 我使它成为更笼统的问题。Which state to move when we have more than one choices for next state?

如何在NFA中处理字符串？

_{我正在考虑将自动机模型作为接受器，如果它属于自动机的语言，则接受一个字符串。（注意：我们可以将自动机作为转换器），下面是上面示例的答案}

在上面的NFA中，我们找到5个管状对象：

1.  ? :  {a, b}  
2.  Q :  {q1, ,q2, q3}  
3.  q1:  initial state
4.  F :  {q3}       <---F is set of final state
5.  ? : Transition rules in above diagram: 
         ?(q1, a) ? { q1, q2 }
         ?(q1, b) ? { q1 }
         ?(q2, b) ? { q3 } 

例子中的有限自动机实际上是一个NFA，因为在生产规则中?(q1, a) ? { q1, q2 }，如果我们a在当前状态为时得到符号，q1则下一个状态可以是q1或q2（多个选择）。因此，当我们在NFA中处理字符串时，a当当前状态为时，无论它们是要处理的符号，我们都会获得额外的路径q1。

如果存在一些可能的移动顺序，则字符串会被NFA接受，这将使机器在字符串处理结束时处于最终状态。所有具有F从初始状态到集合中任何最终状态的路径的所有字符串的集合称为NFA语言：

我们还可以写：“ NFA定义了什么语言？” 如：

L（nfa）= {w？？* | ？*（q ₁，w）？F ？？}

_{当我是新手时，这太复杂了，我无法理解，但实际上不是}

L（nfa） 说：所有字符串都由语言符号= =（w？？*）组成。如果 (|)在处理w形式初始状态（=？*（q1，w））之后获得的状态集包含最终状态集中的某些状态（因此与最终状态的交集不为空=？*（q1，w）？F ？？）。因此，在？*中处理字符串时，我们需要跟踪所有可能的路径。

Example-1：abab尽管在NFS之上处理字符串：

--?(q1)---a---?(q1)---b---?(q1)---a---?(q1)---b---?(q1)
     \                       \ 
      a                       a  
       \                       \
        ?                       ?
       (q2)                     (q2)---b---?((q3))
        |                      
        b                      
        |                      
        ?                                 
       (q3)                   
        |
        a
        |
       halt  

上图显示：如何abab在NFA中处理字符串？

一个停止：手段字符串不能完全处理，因此它不能在这个路径中考虑接受的字符串

字符串abab可以在两个方向上完全处理，因此？*（q1，w）= {q1，q3}。

？*（q1，w）与最终状态集的交集为{q3}：

                  {q1, q3} ? F 
             ==>  {q1, q3} ? {q3}     
             ==>  {q3}  ?  ? 

这样，字符串ababa使用语言L（nfa）。

示例2：来自？*的字符串是abba，以下是如何处理：

--?(q1)---a---?(q1)---b---?(q1)---b---?(q1)---a---?(q1)
     \                                   \ 
      a                                   a  
       \                                   \
        ?                                   ?
       (q2)                                (q2)
        |                      
        b                      
        |                      
        ?                                 
       (q3)                   
        |
        b
        |
       halt    

对于abba可达状态的字符串集为？*（q1，w）= {q1，q2}，并且在此集中没有状态是最终状态，这意味着=>其与F的交点是？一个空集，因此字符串abba不是可接受的字符串（并且不是语言）。

这是我们在非确定性有限自动机中处理字符串的方式。

一些其他重要说明：

• 在有限自动机的情况下，确定性和非确定性模型均具有同等能力。非确定性模型没有定义语言的额外功能。因此，NFA和DFA的范围与常规语言相同。（并非所有自动化类别都如此，例如PDA！= NPDA的范围）

• 非确定性模型对于理论目的更有用，相对而言，它可以得出结论。出于实现目的，我们始终希望使用确定性模型（为了效率而最小化）。幸运的是，在有限自动元类中，每个非确定性模型都可以转换为等效的确定性模型。我们有将NFA转换为DFA的算法方法。

• 由DFA中的单个状态表示的信息可以由NFA状态的组合表示，因此NFA中的状态数小于其等效DFA。（证明是可用的numberOfStates（DFA）<= 2 power numberOfStates（NFA），因为所有设置组合都是powerset）

上述常规语言的DFA如下：

使用此DFA，您将始终为？*中的任何字符串找到从初始状态到最终状态的唯一路径，而不是置位，您将进入单个可到达的最终状态，并且如果该状态属于final集，则表示输入字符串为被接受的字符串（语言），否则不/

（您的表示.*ab与(a + b)*ab理论科学中通常相同，.除连接外我们不使用点运算符）