计算理论-有限自动机(FA)

有限自动机是一种数学模型，用于表示和分析有限状态的计算过程。它包括确定性有限自动机（DFA）和非确定性有限自动机（NFA），广泛应用于语言识别和编译技术等领域。

有限自动机结构

有限自动机（FA）由五部分组成：

• 状态集合：Q，表示有限个状态，用大写字母表示。

• 输入字母表：Σ，表示输入的符号集合，用小写字母表示。

• 转移函数：δ，表示从状态q_i到状态q_j的转换条件，用δ(q_i,a)=q_j表示。

• 初始状态：q_0，表示初始状态。

• 接受状态集合：F，表示接受的状态集合。

确定的有限自动机（DFA）

定义

DFA是一种确定性的有限自动机，即从初始状态到任意一个接受状态的转换路径都有唯一确定的方向。

记作M=(K, Σ, δ, q_0, F):其中

• K是状态集合，**q₀**是初始状态，F是接受状态集合。

• Σ是输入字母表，δ是转移函数，δ(q_i,a)=q_j表示从状态q_i通过输入符号a转移到状态q_j。

• δ(q_i,a)表示从状态q_i通过输入符号a转移到状态q_j。

• F是终止状态集合，q_i∈F表示状态**q_i**是终止状态。

K={q₀,q₁,…,q_n} ， Σ={0,1}
δ(q₀,0)=q₂ δ(q₀,1)=q₁
δ(q₁,0)=q₂ δ(q₁,1)=q₀
δ(q₂,0)=q₂ δ(q₂,1)=q₀
F={q₀}

写成表格就是这样

	0	1
q0	q2	q1
q1	q2	q0
q2	q2	q0

不确定的有限自动机（NFA）

定义

NFA是一种不确定的有限自动机，即从初始状态到任意一个接受状态的转换路径可能有多条。

记作M=(K, Σ, δ, q₀, F)
与DFA的定义类似，只是δ(q_i,a)可能有多条路径，表示从状态q_i通过输入符号a可以转移到状态**q_j**的集合。

多映射

例如
δ(q₀,0)={q₂，q₃}

	0	1
q₀	{q₁, q₂}	{q₁}
q₁	{q₁, q₂}	{q₀}
q₂	{q₂}	{q₀}

NFA转换成DFA

定理

如果语言L可由一个NFA M所接收，则必然存在一个DFA M’，使得T(M’)=L。

例如

K^`状态集合就是左侧那一列。

那F^`怎么定义的呢？

别忘了新生成的F^`与原来的F交集不为空，那么显然，找到含有F中元素的新[q,q,q,]就行了

具有ε转移的NFA（ε-NFA）

定义

具有空转移的NFA是指，对于任意状态q，δ(q,ε)∈F。

delta函数的扩充

δ^(q₀,0)={q₀，q₁,q₂}!=δ(q₀,0)={q₀}

参考

《计算理论ppt》