正则表达式 – 转换中的歧义：如何在NFA中处理字符串？

我从你的例子的基础开始,以便人们可以发现它有用
任何 class of automata都可以有两种形式：

>确定性
>非确定性.

在确定性模型中：我们只有一个选择(或者说没有选择)从一个congratulation移动到下一个configuration.
在Finite Automate的确定性模型(DFA)中：对于状态(Q)和语言符号(Σ)的每种可能组合,我们总是具有唯一的下一状态.

Definition of transition function for DFA: δ:Q×Σ → Q

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

因此,在DFA中,从一个状态到下一个状态,每个可能的移动都是明确的.

然而,
在非确定性模型中：我们可以为下一个配置提供多个选择.
并且在有限自动机(NFA)的非确定性模型中：输出是状态(Q)和语言符号(Σ)的某种组合的状态集.

NFA的转移函数的定义：δ：Q×Σ→2Q =?Q

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

在NFA中,我们可以为下一个州提供多个选择.那就是你在过渡NFA中所谓的歧义.

(你的例子)
假设语言符号是Σ= {a,b},语言/正则表达式是(a b)* ab.这种语言的有限自动机可能如下：

Your question is: Which state to move when we have more than one choices for next state?
I make it more general question.

如何在NFA中处理字符串？

我正在考虑将自动机模型作为接受器,如果它属于自动机语言,则接受字符串.(注意：我们可以将自动机作为换能器),下面是我的回答以上示例

在上面的NFA中,我们找到了5个tapular对象：

1.  Σ :  {a,b}  
2.  Q :  {q1,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}中,如果我们得到一个符号,而当前状态是q1,那么下一个状态可以是q1或q2(多个选择) ).因此,当我们在NFA中处理字符串时,我们会获得额外的路径,只要它们是一个符号a进行处理,而当前状态为q1.

如果存在一些可能的移动序列,则会在字符串处理结束时将机器置于最终状态,NFA接受字符串.并且所有字符串的集合都有一些路径可以从初始状态到达集合F中的任何最终状态,称为NFA的语言：

我们也可以写一下,“NFA定义的语言是什么？”如：

L(nfa) = { w ? Σ* | δ*(q₁,w) ∩ F ≠ ?}

当我是新人时,这对我来说太复杂了,但实际上并非如此

L(nfa)说：所有字符串都由语言符号组成=(w?Σ*)是用语言表达的; if(|)在处理w形式初始状态(=δ*(q1,w))后得到的状态集包含最终状态集中的一些状态(因此与最终状态的交集不为空=δ*(q1,w)∩F≠?).因此,在处理Σ*中的字符串时,我们需要跟踪所有可能的路径.

示例1：在NFS上面处理字符串abab：

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

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

停止：表示字符串无法完全处理,因此不能将此路径中的字符串视为已接受的字符串

字符串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,q2}并且在该集合中没有状态是最终状态,这意味着=>它与F的交集是一个空集,因此字符串abba不是一个可接受的字符串(而不是语言).

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

一些额外的重要说明：

>在有限自动机的情况下,确定性和非确定性模型同样有能力.非确定性模型没有额外的定义语言的能力.
因此,NFA和DFA的范围与常规语言相同. (这不是所有类自动化的例子,例如PDA的范围！= NPDA)
>非确定性模型对于理论目的更有用,相对论文来说是有用的.鉴于实现目的,我们总是希望确定性模型(为效率最小化).幸运的是,在有限autometa类中,每个非确定性模型都可以转换为等效的确定性模型.我们有算法方法到convert an NFA into DFA.
>由DFA中的单个状态表示的信息可以由NFA状态的组合表示,因此NFA中的状态数小于其等效DFA. (证据可用numberOfStates(DFA)< = 2 power numberOfStates(NFA),因为所有设置组合都是powerset)
以上常规语言的DFA如下：

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

(你的表达.* ab和(a b)* ab通常在我们不使用的理论科学中相同.点运算符,然后连接)