不知道写点什么,所以记一下,以防失忆

🤖

本文内容含AI生成内容

DFA

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

定义

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

  • QQ 是一个有限的状态集合。
  • Σ\Sigma 是一个有限的输入符号集合。
  • δ\delta 是状态转移函数,它将 Q×ΣQ \times \Sigma 映射到 QQ。也就是说,对于当前状态和输入符号,DFA 有唯一的下一个状态。
  • q0q_0 是初始状态,q0Qq_0 \in Q
  • FF 是接受状态集合,FQF \subseteq Q

工作原理

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

示例

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

1
2
3
4
5
6
7
8
+---0---+
| |
v |
q0 --1--> q1 --0--> q2
^ | |
| +---1---+
|
+---0,1---+

这里,Q={q0,q1,q2}Q = \{q_0, q_1, q_2\},Σ={0,1}\Sigma = \{0, 1\},q0q_0 是初始状态,F={q2}F = \{q_2\}。状态转移函数 δ\delta 可以表示为:

  • δ(q0,0)=q0\delta(q_0, 0) = q_0
  • δ(q0,1)=q1\delta(q_0, 1) = q_1
  • δ(q1,0)=q2\delta(q_1, 0) = q_2
  • δ(q1,1)=q1\delta(q_1, 1) = q_1
  • δ(q2,0)=q0\delta(q_2, 0) = q_0
  • δ(q2,1)=q1\delta(q_2, 1) = q_1

NFA

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

定义

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

工作原理

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

示例

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

1
2
3
4
5
6
7
+---0---+
| |
v |
q0 --0,1--> q0 --0--> q1 --1--> q2
^ |
| +---0,1---+
+---0,1---+

这里,Q={q0,q1,q2}Q = \{q_0, q_1, q_2\},Σ={0,1}\Sigma = \{0, 1\},q0q_0 是初始状态,F={q2}F = \{q_2\}。状态转移函数 δ\delta 包含了一些多值转移和 ϵ\epsilon 转移(这里没有 ϵ\epsilon 转移示例)。

NFA 转 DFA 步骤

步骤 1:确定初始状态

  • 对于 NFA 的初始状态 q0q_0,计算其 ϵ\epsilon-闭包(ϵ\epsilon-closure),记为 C0C_0ϵ\epsilon-闭包是指从某个状态出发,仅通过 ϵ\epsilon 转移能够到达的所有状态的集合。
  • C0C_0 作为 DFA 的初始状态。

步骤 2:状态转移计算

  • 对于 DFA 中的每个状态(这些状态实际上是 NFA 状态的集合),对于输入符号集合 Σ\Sigma 中的每个符号 aa,计算该状态在符号 aa 下的转移。
  • 具体来说,对于 DFA 的状态 SS,计算 δ(S,a)=ϵ-closure(qSδ(q,a))\delta'(S, a) = \epsilon\text{-closure}(\bigcup_{q \in S} \delta(q, a)),其中 δ\delta' 是 DFA 的状态转移函数。

步骤 3:接受状态确定

  • 如果 DFA 的某个状态 SS 包含 NFA 的接受状态集合 FF 中的至少一个状态,则将 SS 标记为 DFA 的接受状态。

步骤 4:重复步骤 2 和 3

  • 不断重复步骤 2 和 3,直到没有新的 DFA 状态产生为止。

示例

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

状态 0 1 ϵ\epsilon
q0q_0 {q0,q1}\{q_0, q_1\} {q0}\{q_0\} {}\{\}
q1q_1 {}\{\} {q2}\{q_2\} {}\{\}
q2q_2 {}\{\} {}\{\} {}\{\}

初始状态为 q0q_0,接受状态为 q2q_2

  • 初始状态ϵ-closure(q0)={q0}\epsilon\text{-closure}(q_0) = \{q_0\},所以 DFA 的初始状态为 {q0}\{q_0\}
  • 状态转移计算
    • 对于状态 {q0}\{q_0\},δ({q0},0)=ϵ-closure(δ(q0,0))=ϵ-closure({q0,q1})={q0,q1}\delta'(\{q_0\}, 0) = \epsilon\text{-closure}(\delta(q_0, 0)) = \epsilon\text{-closure}(\{q_0, q_1\}) = \{q_0, q_1\}
    • δ({q0},1)=ϵ-closure(δ(q0,1))=ϵ-closure({q0})={q0}\delta'(\{q_0\}, 1) = \epsilon\text{-closure}(\delta(q_0, 1)) = \epsilon\text{-closure}(\{q_0\}) = \{q_0\}
    • 对于状态 {q0,q1}\{q_0, q_1\},δ({q0,q1},0)=ϵ-closure(δ(q0,0)δ(q1,0))=ϵ-closure({q0,q1}{})={q0,q1}\delta'(\{q_0, q_1\}, 0) = \epsilon\text{-closure}(\delta(q_0, 0) \cup \delta(q_1, 0)) = \epsilon\text{-closure}(\{q_0, q_1\} \cup \{\}) = \{q_0, q_1\}
    • δ({q0,q1},1)=ϵ-closure(δ(q0,1)δ(q1,1))=ϵ-closure({q0}{q2})={q0,q2}\delta'(\{q_0, q_1\}, 1) = \epsilon\text{-closure}(\delta(q_0, 1) \cup \delta(q_1, 1)) = \epsilon\text{-closure}(\{q_0\} \cup \{q_2\}) = \{q_0, q_2\}
    • 对于状态 {q0,q2}\{q_0, q_2\},δ({q0,q2},0)=ϵ-closure(δ(q0,0)δ(q2,0))=ϵ-closure({q0,q1}{})={q0,q1}\delta'(\{q_0, q_2\}, 0) = \epsilon\text{-closure}(\delta(q_0, 0) \cup \delta(q_2, 0)) = \epsilon\text{-closure}(\{q_0, q_1\} \cup \{\}) = \{q_0, q_1\}
    • δ({q0,q2},1)=ϵ-closure(δ(q0,1)δ(q2,1))=ϵ-closure({q0}{})={q0}\delta'(\{q_0, q_2\}, 1) = \epsilon\text{-closure}(\delta(q_0, 1) \cup \delta(q_2, 1)) = \epsilon\text{-closure}(\{q_0\} \cup \{\}) = \{q_0\}
  • 接受状态确定
    • 状态 {q0,q2}\{q_0, q_2\} 包含 NFA 的接受状态 q2q_2,所以 {q0,q2}\{q_0, q_2\} 是 DFA 的接受状态。

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

状态 0 1
{q0}\{q_0\} {q0,q1}\{q_0, q_1\} {q0}\{q_0\}
{q0,q1}\{q_0, q_1\} {q0,q1}\{q_0, q_1\} {q0,q2}\{q_0, q_2\}
{q0,q2}\{q_0, q_2\} {q0,q1}\{q_0, q_1\} {q0}\{q_0\}

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