DFA与NFA的故事(一)

2020-04-25 约 1681 字预计阅读 4 分钟

对于DFA和NFA形式定义的一些理解，以及正则运算封闭性和DFA与NFA等价性的证明，也就是说DFA的故事是属于NFA的，是特例和常规的故事呢。

对于确定型有穷自动机（DFA）的一些认识

对于确定型有穷自动机，也即deterministic finite automaton 或者说 deterministischer endlicher Automat，我们可以给出相应的形式定义，这里借用Tobias教授在课上给的定义：

1
2
3
4
5
6
7
8


Ein deterministischer endlicher Automat (deterministic infinite automaton, DFA)
 M = (Q, ∑, δ, q0, F), besteht aus

einer endlichen Menge von Zuständen Q,
einem (endlichen) Eingabealphabet ∑,
einer (totalen!) Übergangsfunktion  δ: Q × ∑ → Q,
einem Startzustand q0 ∈ Q, und
einer Menge F ⊆ Q von Endzuständen (akzeptierenden Zust.)

也就是说我们首先有一个有穷状态集 Q 包括这个自动机的所有的状态(states)，然后一个输入字母表 ∑，包括所有可能的输入，一个转移函数 δ，从现在的状态接受一个输入到一个新状态的映射(这里还有一个扩展的转移函数后面再说), 一个初始状态 q0 表示从哪开始，和这个自动机的接收状态的集合 F 作为 Q 的一个子集。关于这个扩展转移函数我们可以做类似的定义：

1

δ: Q × ∑* → Q

这里的∑*代表的是由∑构成的字符串，也就是说自动机也可以对字符串的输入进行反应，这也是为了方便而定义的。该装置接受的语言记作：

1

L(M):= {w∈∑*|δ(q0, w)∈F}

就是说从初始状态出发读完输入串w之后所处的状态是一个接受状态，那么就接受这个串。被DFA识别的语言也叫正则语言。

对于非确定型有穷自动机（NFA）的一些认识

对于非确定型有穷自动机(nondeterministic finite automaton 或者说 nichtdeterministischer endlicher Automat)与确定型的区别就在于非确定性：下一个状态可以不唯一确定，可以进行ε移动，多种选择(含0种选择)，我们还是来看看Tobias教授ppt上的定义：

1
2
3
4
5


Ein nichtdeterministischer endlicher Automat (nondeterministic infinite automaton, NFA) ist ein 5-Tupel N = (Q, ∑, δ, q0, F), so dass
   Q, ∑, q0 und F sind wie bei einem DFA
   δ: Q × ∑ → P(Q)
   P(Q) = Menge aller Teilmengen von Q = 2^Q.
   Alternative: Relation δ ⊆ Q × ∑ × Q.

请注意这里的输入字母表 ∑ 是原本的 ∑和 ε的并, 也就还要加上长度为0的符号ε; 然后对于这里的转移函数 δ 在当前状态下读一个符号进入一个状态，因为不确定性有多种选择，所以进入多个状态，这里要用一个幂集来表示，也就是说这里的新状态是若干个Q的状态。同样这里对于转移函数 δ的扩展可以把 Q 改写为 P(Q),将原本的某一个状态扩展到多个状态的集合，这样就构成了多个备份。该装置接受的语言记作：

1

L(N):= {w∈∑*|δ({q0}, w) ∩ F ≠ Ø}

现在我们自然而然地会去想DFA与NFA之间有怎样的故事呢？DFA和NFA的能力是否一样？这也就是说它们是否识别同样的语言呢？我们知道DFA识别的语言NFA也可以识别，那么NFA识别的语言DFA是否也可以识别呢？这就涉及到它们的等价性的问题了。

正则运算的封闭性

我们想要去证明DFA和NFA的等价性还是先证明正则运算的封闭性(有时间再写吧，主要还是构造法)

DFA与NFA的等价性

我们首先给出关于"等价"的定义，即两台机器识别同样的语言，它们的功能是一样的但是内部构造可能不一样；状态数，转移函数可能都不一样。于是我们接下来要证明的就是：每台NFA都有等价的DFA。(这里有一些题外话如果是下推自动机或图灵机确定和非确定的故事就又需要我们去探索了)

这里我们就需要用到构造法来证明了hh

证明思路：对于给定的NFA，构造等价DFA，用DFA来模拟NFA，也即让DFA记住NFA的所有分支(理论上可行，因为NFA的k个状态是有穷的，于是所有可能的状态的子集合2^k个也是有穷的)，同时引入ε闭包的概念，对于每个状态子集合，经ε移动可达到的新状态子集合。

下面给出严格的证明：

1
2
3


设 NFA N = (Q, ∑, δ, q0, F),构造 DFA M = (Q', ∑, δ', q0', F'), L(M) = L(N).
令Q' = P(Q). 对R∈Q'和a∈∑, E(R)={q|从R出发沿0个或多个ε移动可达q};
δ'(R,a)=∪(r∈R)(R ∩ F ≠ Ø).

写在最后

这一周THEO的课重要的部分大概是这些了，还有一些基本概念就没有写上来，至于这些语言的概念请参考Chomsky hierarchy, 下周的课看ppt应该是和正则语言以及上下文无关文法有关，也挺期待的呢。

目录