4

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

4

2 回答 2

5

我从你的例子开始，这样人们就会发现它很有帮助
任何类型的自动机都可以有两种形式：

  • 确定性
  • 非确定性的。

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

DFA 的转移函数定义：δ:Q×Σ → Q 

δ(q0, a) → q1
            ^ only single choice

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

而
在非确定性模型中：对于下一个配置，我们可以有多个选择。
在有限自动机（NFA）的非确定性模型中：输出是状态（Q）和语言符号（Σ）的某种组合的状态集。

NFA 的转移函数定义：δ:Q×Σ → 2 Q = ⊆ 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 个 Tapular 对象：

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 1 , w) ∩ F ≠ ∅}

当我是新手时，这对我来说太复杂了，无法理解，但实际上不是

L(nfa) 表示：所有字符串都由语言符号组成 = (w ⊆ Σ* ) 在语言中；如果 经过形式初始状态（=δ*(q1, w) ）(|)处理后得到的w状态集合包含最终状态集合中的一些状态（因此与最终状态的交集不为空 = δ*(q1, w) ∩ F ≠ ∅）。因此，在处理 Σ* 中的字符串时，我们需要跟踪所有可能的路径。

示例 1abab ：通过 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 如下：

(a+b)*ab-dfa

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

（你的表达通常在理论科学.*ab中(a + b)*ab是相同的，我们不使用.点运算符而不是连接）

于 2013-03-27T14:23:11.113 回答
0

与此类正则表达式的匹配通过回溯发生。当对下一个状态有歧义时，评估会选择第一个选择并记住它做出了选择。如果采用第一个选择导致匹配失败，则评估将回溯到它所做的最后一个选择，并尝试从该状态下一个可用的选择。

我不确定这种机制是否映射到严格的 DFA。

于 2013-03-25T14:53:54.477 回答