不知道写点什么,所以记一下,以防失忆
DFA
确定有限自动机(Deterministic Finite Automaton,DFA)是一种计算模型,常用于模式匹配、词法分析等领域。
定义
一个 DFA 可以用一个五元组 (Q,Σ,δ,q0,F) 来表示,其中:
- Q 是一个有限的状态集合。
- Σ 是一个有限的输入符号集合。
- δ 是状态转移函数,它将 Q×Σ 映射到 Q。也就是说,对于当前状态和输入符号,DFA 有唯一的下一个状态。
- q0 是初始状态,q0∈Q。
- F 是接受状态集合,F⊆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},Σ={0,1},q0 是初始状态,F={q2}。状态转移函数 δ 可以表示为:
- δ(q0,0)=q0
- δ(q0,1)=q1
- δ(q1,0)=q2
- δ(q1,1)=q1
- δ(q2,0)=q0
- δ(q2,1)=q1
NFA
非确定有限自动机(Non-Deterministic Finite Automaton,NFA)也是一种计算模型,与 DFA 相比,它在状态转移上具有不确定性。
定义
一个 NFA 同样可以用一个五元组 (Q,Σ,δ,q0,F) 来表示,不过状态转移函数 δ 的定义有所不同。这里,δ 将 Q×(Σ∪{ϵ}) 映射到 2Q,即对于当前状态和输入符号(可以是 ϵ,表示空转移),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},Σ={0,1},q0 是初始状态,F={q2}。状态转移函数 δ 包含了一些多值转移和 ϵ 转移(这里没有 ϵ 转移示例)。
NFA 转 DFA 步骤
步骤 1:确定初始状态
- 对于 NFA 的初始状态 q0,计算其 ϵ-闭包(ϵ-closure),记为 C0。ϵ-闭包是指从某个状态出发,仅通过 ϵ 转移能够到达的所有状态的集合。
- 将 C0 作为 DFA 的初始状态。
步骤 2:状态转移计算
- 对于 DFA 中的每个状态(这些状态实际上是 NFA 状态的集合),对于输入符号集合 Σ 中的每个符号 a,计算该状态在符号 a 下的转移。
- 具体来说,对于 DFA 的状态 S,计算 δ′(S,a)=ϵ-closure(⋃q∈Sδ(q,a)),其中 δ′ 是 DFA 的状态转移函数。
步骤 3:接受状态确定
- 如果 DFA 的某个状态 S 包含 NFA 的接受状态集合 F 中的至少一个状态,则将 S 标记为 DFA 的接受状态。
步骤 4:重复步骤 2 和 3
- 不断重复步骤 2 和 3,直到没有新的 DFA 状态产生为止。
示例
假设我们有一个简单的 NFA,其状态转移表如下:
状态 |
0 |
1 |
ϵ |
q0 |
{q0,q1} |
{q0} |
{} |
q1 |
{} |
{q2} |
{} |
q2 |
{} |
{} |
{} |
初始状态为 q0,接受状态为 q2。
- 初始状态:ϵ-closure(q0)={q0},所以 DFA 的初始状态为 {q0}。
- 状态转移计算:
- 对于状态 {q0},δ′({q0},0)=ϵ-closure(δ(q0,0))=ϵ-closure({q0,q1})={q0,q1}。
- δ′({q0},1)=ϵ-closure(δ(q0,1))=ϵ-closure({q0})={q0}。
- 对于状态 {q0,q1},δ′({q0,q1},0)=ϵ-closure(δ(q0,0)∪δ(q1,0))=ϵ-closure({q0,q1}∪{})={q0,q1}。
- δ′({q0,q1},1)=ϵ-closure(δ(q0,1)∪δ(q1,1))=ϵ-closure({q0}∪{q2})={q0,q2}。
- 对于状态 {q0,q2},δ′({q0,q2},0)=ϵ-closure(δ(q0,0)∪δ(q2,0))=ϵ-closure({q0,q1}∪{})={q0,q1}。
- δ′({q0,q2},1)=ϵ-closure(δ(q0,1)∪δ(q2,1))=ϵ-closure({q0}∪{})={q0}。
- 接受状态确定:
- 状态 {q0,q2} 包含 NFA 的接受状态 q2,所以 {q0,q2} 是 DFA 的接受状态。
最终得到的 DFA 状态转移表如下:
状态 |
0 |
1 |
{q0} |
{q0,q1} |
{q0} |
{q0,q1} |
{q0,q1} |
{q0,q2} |
{q0,q2} |
{q0,q1} |
{q0} |
通过以上步骤,我们成功地将 NFA 转换为了 DFA。