任何 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 ⊆ Σ* | δ*(q1,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通常在我们不使用的理论科学中相同.点运算符,然后连接)