计算理论-有限自动机(FA)
有限自动机结构
有限自动机（FA）由五部分组成：
- 状态集合：Q，表示有限个状态，用大写字母表示。
- 输入字母表：Σ，表示输入的符号集合，用小写字母表示。
- 转移函数：δ，表示从状态q_i到状态q_j的转换条件，用δ(q_i,a)=q_j表示。
- 初始状态：q_0，表示初始状态。
- 接受状态集合：F，表示接受的状态集合。
确定的有限自动机（DFA）
定义
DFA是一种确定性的有限自动机，即从初始状态到任意一个接受状态的转换路径都有唯一确定的方向。
记作M=(K, Σ, δ, q_0, F):其中
- K是状态集合，**q~0~**是初始状态，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~0~,q~1~,…,q~n~} ， Σ={0,1}
δ(q~0~,0)=q~2~ δ(q~0~,1)=q~1~
δ(q~1~,0)=q~2~ δ(q~1~,1)=q~0~
δ(q~2~,0)=q~2~ δ(q~2~,1)=q~0~
F={q~0~}
写成表格就是这样
| 0 | 1 | |
|---|---|---|
| q~0~ | q~2~ | q~1~ |
| q~1~ | q~2~ | q~0~ |
| q~2~ | q~2~ | q~0~ |
不确定的有限自动机（NFA）
定义
NFA是一种不确定的有限自动机，即从初始状态到任意一个接受状态的转换路径可能有多条。
记作M=(K, Σ, δ, q~0~, F)
与DFA的定义类似，只是δ(q~i~,a)可能有多条路径，表示从状态q~i~通过输入符号a可以转移到状态**q~j~**的集合。
多映射
例如
δ(q~0~,0)={q~2~，q~3~}
| 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~,0)={q~0~，q~1~,q~2~}!=δ(q~0~,0)={q~0~}
