编译原理:NFA转DFA

DFA

确定有限自动机(Deterministic Finite Automaton,DFA)是一种计算模型,常用于模式匹配、词法分析等领域。

定义

一个 DFA 可以用一个五元组 (Q,Σ,δ,q0,F)(Q, \Sigma, \delta, q_0, F)(Q,Σ,δ,q0​,F) 来表示,其中：

• QQQ 是一个有限的状态集合。
• Σ\SigmaΣ 是一个有限的输入符号集合。
• δ\deltaδ 是状态转移函数,它将 Q×ΣQ \times \SigmaQ×Σ 映射到 QQQ。也就是说,对于当前状态和输入符号,DFA 有唯一的下一个状态。
• q0q_0q0​ 是初始状态,q0∈Qq_0 \in Qq0​∈Q。
• FFF 是接受状态集合,F⊆QF \subseteq QF⊆Q。

工作原理

DFA 从初始状态开始,根据输入符号和状态转移函数不断地转移状态。当输入字符串处理完毕后,如果 DFA 处于接受状态集合中的某个状态,则认为该字符串被 DFA 接受；否则,该字符串被拒绝。

示例

假设我们有一个 DFA 用于识别以 01 结尾的二进制字符串,其状态转移图如下：

+---0---+
    |       |
    v       |
q0 --1--> q1 --0--> q2
 ^         |       |
 |         +---1---+
 |
 +---0,1---+

NFA

非确定有限自动机(Non-Deterministic Finite Automaton,NFA)也是一种计算模型,与 DFA 相比,它在状态转移上具有不确定性。

定义

一个 NFA 同样可以用一个五元组 (Q,Σ,δ,q0,F)(Q, \Sigma, \delta, q_0, F)(Q,Σ,δ,q0​,F) 来表示,不过状态转移函数 δ\deltaδ 的定义有所不同。这里,δ\deltaδ 将 Q×(Σ∪{ϵ})Q \times (\Sigma \cup \{\epsilon\})Q×(Σ∪{ϵ}) 映射到 2Q2^Q2Q,即对于当前状态和输入符号(可以是 ϵ\epsilonϵ,表示空转移),NFA 可能有多个下一个状态。

工作原理

NFA 在处理输入字符串时,对于每个输入符号,它可以同时尝试多个可能的状态转移。如果存在一条从初始状态到某个接受状态的路径,使得沿着该路径处理完整个输入字符串,则认为该字符串被 NFA 接受。

示例

考虑一个 NFA 用于识别包含 01 子串的二进制字符串,其状态转移图如下：

+---0---+
    |       |
    v       |
q0 --0,1--> q0 --0--> q1 --1--> q2
             ^         |
             |         +---0,1---+
             +---0,1---+

NFA 转 DFA 步骤

步骤 1：确定初始状态

步骤 2：状态转移计算

步骤 3：接受状态确定

步骤 4：重复步骤 2 和 3

示例

假设我们有一个简单的 NFA,其状态转移表如下：

最终得到的 DFA 状态转移表如下：

通过以上步骤,我们成功地将 NFA 转换为了 DFA。