计算理论-有限自动机(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是状态集合，**q0**是初始状态，F是接受状态集合。
• Σ是输入字母表，δ是转移函数，δ(qi,a)=qj表示从状态qi通过输入符号a转移到状态qj。
• δ(qi,a)表示从状态qi通过输入符号a转移到状态qj。
• F是终止状态集合，qi∈F表示状态**qi**是终止状态。

K={q0,q1,…,qn} ， Σ={0,1} δ(q0,0)=q2 δ(q0,1)=q1 δ(q1,0)=q2 δ(q1,1)=q0 δ(q2,0)=q2 δ(q2,1)=q0 F={q0}

写成表格就是这样

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

定义

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

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

多映射

例如 δ(q0,0)={q2，q3}

NFA转换成DFA

定理

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

例如

2024-10-13-160346

2024-10-13-155624

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

那F`怎么定义的呢？

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

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

定义

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

delta函数的扩充

δ^(q0,0)={q0，q1,q2}!=δ(q0,0)={q0}

2024-10-13-163151

2024-10-13-163435

参考

《计算理论ppt》