NFA的接受集 a,b 。 对于x∈∑*若集合fS0,冲含有Z 中的元素（终态)，则说明，至 少存在一条从初态S到某一终态 的路径，此路径上的符号之连接 恰为x,此时，我们称为M所接 注意，NFA识别输入符号串 受 时有一个试探过程，为了能 所有为M所接受的符号串之集称 走到终态，往往要走许多弯 0 为NFAM的接受集（或识别集）， 路（带回溯），这影响了FA 的效率。 记作L(M).即L(M)={x/fSo, X门Z≠☑，X∈8 能否提高其工作效率就是我 例3.1给定M=(S,A,B,C,{a,b} 们下一小节讨论的课题。事 实上 f,S,{C),其状态转换图见右。由 对任一NFAM,总可 个AM1使 图可知M是一NFA。 L(M)=L(M0成立。这就是 M识别符号串ababb的路径为 NFA与DFA的等价性。 S(a)-→A(b)→B(a)-→A(b)-B(b) →C(接受)。（参见书中P60的表） NFA的接受集 • 对于x*,若集合f(S0,x)中含有Z 中的元素（终态），则说明，至 少存在一条从初态S0到某一终态 的路径，此路径上的符号之连接 恰为x，此时，我们称x为M所接 受 • 所有为M所接受的符号串之集称 为NFA M的接受集（或识别集）， 记作 L(M).即 L(M)={x | f(S0, x ) Z  , x} • 例3.1 给定M= ({S,A,B,C}, {a,b}, f , S ,{C}),其状态转换图见右。由 图可知M是一NFA。 • M识别符号串ababb的路径为 S(a)→A(b)→B(a)→A(b)→B(b) →C(接受)。(参见书中P60的表) S A B C a a,b a b b a a 注意，NFA识别输入符号串 时有一个试探过程，为了能 走到终态，往往要走许多弯 路（带回溯），这影响了FA 的效率。 能否提高其工作效率就是我 们下一小节讨论的课题。事 实上，对任一NFA M，总可 构造一个DFA M’，使 L(M’)=L(M)成立。这就是 NFA与DFA的等价性