过渡中的歧义:如何在NFA中处理字符串? [英] Ambiguity in transition: How to process string in NFA?
问题描述
我已经根据给定的正则表达式制作了DFA，以匹配测试字符串.在某些情况下会出现.*. (例如.*ab).假设现在计算机处于状态1.在DFA中，.*表示所有字符到其自身的过渡，而从状态1到a的另一过渡是"a".如果测试字符串包含"a"，则可能是过渡，因为从状态1开始，计算机可以进入两种状态，这在DFA中是不可能的.
I have made DFA from a given regular expression to match the test string. There are some cases in which .* occurs. ( for example .*ab ) . Let say now the machine is in state 1. In the DFA, .* refers to the transition for all the characters to itself and another transition for a from the state 1 for 'a'. If test string contains 'a' then what could be the transition because from state 1, machine can go to two states that is not possible in DFA.
推荐答案
我从基础示例开始，以便对您有帮助
任何自动机类可以具有两种形式:
I start with fundamental with your example so that one can find it helpful
Any class of automata can have two forms:
- 确定性
- 不确定性.
在确定性模型中，我们只有一个选择(或者说没有选择)才能从一个祝贺到下一个配置.
在有限自动化(DFA):对于状态(Q)和语言符号(Σ)的每种可能组合，我们始终具有唯一的下一个状态.
In Deterministic model: we only have single choice (or say no choice) to move from one congratulation to next configuration.
In Deterministic model of Finite Automate (DFA): for every possible combination of state (Q) and language symbol (Σ), we always have unique next state.
因此，在DFA中，从一个状态到下一个状态的所有可能移动都是确定.
So, In DFA every possible move is definite from one state to next state.
鉴于，
在不确定性模型中，我们可以为下一个配置选择多个选择.
在有限自动机(NFA)的非确定性模型中:对于状态(Q)和语言符号的 some 组合，输出为状态的 组 (Σ).
Whereas,
In Non-Deterministic model: we can have more than one choice for next configuration.
And in Non-deterministaic model of Finite Automata (NFA): output is set of states for some combination of state (Q) and language symbol (Σ).
NFA转移函数的定义:δ:Q×Σ→2 Q =⊆Q
Definition of transition function for NFA: δ:Q×Σ → 2Q = ⊆ Q
δ(q0, a) → {q1, q2, q3}
^ is set, Not single state (more than one choice)
在NFA中，对于下一个状态，我们可以有多个选择.也就是说，您在过渡NFA中称为模糊度.
In NFA, we can have more then one choice for next state. That is you calls ambiguity in transition NFA.
(您的示例)
假设语言符号为Σ = {a, b}，语言/正则表达式为(a + b)*ab.您使用的这种语言的有限自动机可能类似于以下内容:
(your example)
Suppose language symbols are Σ = {a, b} and the language/regular expression is (a + b)*ab. The finite automata for this language you down might be probably like below:
您的问题是:Which state to move when we have more than one choices for next state?
我把它变成更笼统的问题.
Your question is:Which state to move when we have more than one choices for next state?
I make it more general question.
如何在NFA中处理字符串?
我正在考虑将自动机模型作为接受器，如果该字符串属于自动机的语言，则可以接受该字符串.(注意:我们可以使用自动机作为换能器)，下面是上面示例的答案
How to process string in NFA?
I am considering automata model as an acceptor that accept a string if it belong to the language of automata.(Notice: we can have an automaton as a transducer), below is my answer with an above example
在NFA上方，我们找到5个管状物体:
In above NFA, we find 5 tapular objects:
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 }中，如果在当前状态为q1时得到a符号，则下一个状态可以为q1或q2(大于一种选择).因此，当我们在NFA中处理字符串时，当当前状态为q1时，只要要处理的符号a，我们都会获得额外的路径.
The exampled finite automata is an actually an NFA because in production rule δ(q1, a) → { q1, q2 }, if we get a symbol while present state is q1 then next states can be either q1 or q2 (more than one choices). So when we process a string in NFA, we get extra path to travel wherever their is a symbol a to be process while current state is q1.
如果有一些可能的动作序列会在字符串处理结束时将机器置于最终状态，则NFA会接受字符串.那些具有从初始状态到集合F中的任何最终状态的路径的所有字符串的集合称为NFA语言:
A string is accepted by an NFA, if there is some sequence of possible moves that will put the machine in a final state at the end of string processing. And the set of all string those have some path to reach to any final state in set F from initial state is called language of NFA:
我们还可以写:"NFA定义了什么语言?"如:
We can also write, "what is language defined by a NFA?" as:
L(nfa)= {w⊆Σ* | δ*(q 1 ，w)∩F≠∅}
L(nfa) = { w ⊆ Σ* | δ*(q1, w) ∩ F ≠ ∅}
当我是新手时，这太复杂了，以至于我听不懂，但实际上不是.
L(nfa)说:所有字符串都由语言符号组成= =(w⊆Σ*)都是语言；如果(|)在处理w之后从初始状态(=δ*(q1，w))获得的状态集包含最终状态集中的某些状态(因此与最终状态的交集不为空=δ*( q1，w)∩F≠∅).因此，在以Σ*处理字符串时，我们需要跟踪所有可能的路径.
L(nfa) says: all strings consists of language symbols = (w ⊆ Σ* ) are in language; if (|) the set of states get after processing of w form initial state (=δ*(q1, w) ) contains some states in the set of Final states (hence intersection with final states is not empty = δ*(q1, w) ∩ F ≠ ∅). So while processing a string in Σ*, we need to keep track of all the possible paths.
示例1 :尽管在NFS上方也处理字符串abab:
Example-1: to process string abab though above NFS:
--►(q1)---a---►(q1)---b---►(q1)---a---►(q1)---b---►(q1)
\ \
a a
\ \
▼ ▼
(q2) (q2)---b---►((q3))
|
b
|
▼
(q3)
|
a
|
halt
上图显示:如何在NFA中处理字符串abab?
Above diagram show: How to process a string abab in NFA?
暂停:表示字符串无法完全处理，因此不能视为该路径中可接受的字符串
A halt: means string could not process completely so it can't be consider a accepted string in this path
字符串abab可以在两个方向上完全处理，因此δ*(q1，w)= {q1，q3}.
String abab could process completely in two directions so δ*(q1, w) = { q1, q3}.
δ*(q1，w)与最终状态集的交集为{q3}:
and intersection of δ*(q1, w) with set of final states is {q3}:
{q1, q3} ∩ F
==> {q1, q3} ∩ {q3}
==> {q3} ≠ ∅
这样，字符串ababa的语言为L(nfa).
In this way, string ababa is in language L(nfa).
示例2 :来自Σ*的字符串为abba，下面是处理方法:
Example-2: String from Σ* is abba and following is how to process:
--►(q1)---a---►(q1)---b---►(q1)---b---►(q1)---a---►(q1)
\ \
a a
\ \
▼ ▼
(q2) (q2)
|
b
|
▼
(q3)
|
b
|
halt
对于字符串abba，可到达状态的集合为δ*(q1，w)= {q1，q2}，并且该集合中没有状态为最终状态，这意味着=>其与F的交集为∅一个空集合，因此字符串abba不是可接受的字符串(不是语言).
For string abba set of reachable states is δ*(q1, w) = { q1, q2} and no state is final state in this set this implies => its intersection with F is ∅ a empty set, hence string abba is not an accepted string (and not in language).
这是我们在不确定的有限自动机中处理字符串的方式.
This is the way we process a string in Non-deterministic Finite Automata.
一些其他重要说明:
-
在有限自动机的情况下，确定性和非确定性模型均具有同等能力.非确定性模型没有定义语言的额外功能. 因此，NFA和DFA的范围与常规语言相同.
In case of finite automata's both Deterministic and Non-Deterministic models are equally capable. Non-Deterministic model doesn't have extra capability to define a language. hence scope of NFA and DFA are same that is Regular Language. (this is not case for all class of automate for example scope of PDA !=NPDA)
非确定性模型更适合用于理论目的，相对而言，本文可作参考.出于实现目的，我们始终希望使用确定性模型(为效率而最小化的 ).幸运的是，在有限自动元类中，每个非确定性模型都可以转换为等效的确定性模型.我们有将NFA转换为DFA 的算法方法.
Non-deterministic models are more useful for theoretical purpose, comparatively essay to draw. Whereas for implementation purpose we always desire deterministic model (minimized for efficiency). And fortunately in class of finite autometa every Non-deterministic model can be converted into an equivalent Deterministic one. We have algorithmic method to convert an NFA into DFA.
DFA中由单个状态表示的信息可以由NFA状态的组合表示，因此NFA中的状态数小于其等效DFA. (证明是可用的numberOfStates(DFA)< = 2电源numberOfStates(NFA)，因为所有组合组合都是powerset ))
An information represented by a single state in DFA, can be represented by a combination of NFA states, hence number of states in NFA are less than their equivalent DFA. (proof are available numberOfStates(DFA)<= 2 power numberOfStates(NFA) as all set combinations are powerset)
上述常规语言的DFA如下:
The DFA for above regular language is as below:
使用此DFA，您总会发现Σ*中任何字符串从初始状态到最终状态的唯一路径，而不是设置，您将进入单个可到达的最终状态，并且如果该状态属于该输入字符串的最终集合据说是可以接受的字符串(用语言表示)，否则不是/
Using this DFA you will always find a unique path from initial state to final state for any string in Σ* and instead of set you will gets to a single reachable final state and if that state belongs to set of final that input string is said to be accepted string (in language) otherwise not/
(您的表达式.*ab和(a + b)*ab在理论上通常是相同的，除了连接之外，我们不使用.点运算符)
(your expression .*ab and (a + b)*ab are same usually in theoretical science we don't use . dot operator other then concatenation)
这篇关于过渡中的歧义:如何在NFA中处理字符串?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
