确定有限自动机DFA&非确定有限自动机NFA
确定有限自动机DFA&非确定有限自动机NFA
Part 1_自动机介绍:
有穷自动机(finite state automata)是一个识别器，它对每个输入的字符做识别和判断，以确定其能到达的最终状态或状态集和路径，有穷自动机分为两类，即不确定的有穷自动机NFA和确定的有穷自动机DFA[1].
例子1：红绿灯系统： G（绿灯亮了的状态）；R（红灯亮的状态）；Y（黄灯亮的状态）
例子2：零售机（vending machine）。它接受五角和一块的硬币，但是要至少积累到3元才能按下选择，并且只有作出选择才会执行。所以从初始state开始，每一个状态之后都有两种选择：要么投5角，要么投1元；每次投完都会到达一个新的状态（目前投入硬币总数）。
Part 2_专用名词解释:
在介绍DFA和NFA之前，先介绍几个名词：
alphabet 字母表：符号的有限集合。 记作： Σ 例如：{a, b, ... , x, m}
strings 字符串： 通常我们用到建立在 Σ 上的字符串：有穷的符号序列。 例如：对于 Σ={a, b, c}, “ababc” 就是 Σ 上的一个字符串。
languages 语言：通常我们也只用建立在Σ上的语言，语言就是多个字符串的集合。例如 {ababc, ab, bc, ..}
sentences 句子：句子是语言集合中元素（字符串）的另一个称呼。
notation 符号：Σ* 是Σ上所有可能的字符串的集合。例如：Σ={a, b}, Σ* = { ε, a, b, ab, ba}
Part 3_DFA:
DFA: Deterministic Finite State 确定的有穷自动机
- 第一种计算模型：用来解决对一个已知字符串，看它是否能被某个自动机所接受。
- 一个DFA有有穷个状态（state），主要分为三种状态：
- 初始状态（initial state）：自动机开始的状态；
- 终止状态（final state）：一个DFA至少有一个终止状态；
- 中间状态。
「状态间转换的公式： 状态 x 输入字符 --> 状态」
3. DFA的定义：（共5部分）
A = ( Σ, S, s0, F, N )
- Σ: 输入字母表（alphabet），是一个输入字符的集合。
- S：状态的集合
- s0： 初始状态
- F：终止状态集合 F ⊆ S
- N：转换公式 N:S×Σ → S
4. 「“确定”意味着对于一个输入字符，只有唯一的可能状态」
5. 例子：
从上图我们可以得到一个转换公式表格：
单步表示： N (S0, 0)： 是自动机从s0状态，读取符号0之后的状态。从表格中可以看出N (S0, 0) = S1.
多步表示： N (N (S0, 0), 1) = S2.
** 重要定理： 对S中所有的状态s，所有 Σ*中的字符串 α,β， 有：
N*(s, αβ) = N*(N*(s, α), β)。
6. 最终状态公式 （eventual state function）：
从任意一个状态，经过一个string到达的最终状态的所有可能情况。
表达为： N* : S × Σ* → S
7. 如果一个字符串从一个DFA的初始状态出发，能在某一个终止状态结束，那这个字符串就被这个DFA所接受。所有的这种字符串的集合就是这个自动机的语言（language）。
8. 自动机等同：如果两个自动机接受相同的语言，就说这两个自动机相等。
9. 状态等同：如果对于所有的输入字符串 w， 有并且只有
N*(Sj,w) ∈ F 并且N*(Sk,w) ∈ F （F是final state的集合）
注意，一个非终止状态永远不可能与一个终止状态等同。
10. 状态消除：
1）等同状态消除：如果两个状态等同，那么其中一个可以被消除，来简化自动机。
以上面9.为例，Sk可以被消除， 消除Sk之后的新的自动机A' = (Σ, S', s0, F', N' )
S' = S-Sk
F‘ = F-Sk
N‘（s，w）= （if N（s，w）=Sk then Sj
else N（s，w））
（注意这里有个前提，Sk不能是初始状态，因为初始状态不能被消除。）
2） 无法到达的状态消除：如果一个状态是无法从初始状态到达的，那么它可以被消除，例如下图的S3。
11. 这里有一个传统的分组算法，可以用来最简化自动机，这里不做详细介绍。
Part 4_NFA:
1. NFA(Non-Deeterministic Finite State Automata)不确定的有穷自动机: 对一个输入符号，有两种或两种以上可能对状态，所以是不确定的。
2. NFA可以转换成DFA，NFA和DFA的主要区别在于[1]：
1）DFA没有输入空串之上的转换动作；
2）对于DFA，一个特定的符号输入，有且只能得到一个状态，而NFA就有可能得到一个状态集；
3. NFA的定义：（共5部分）
A = ( Σ, S, s0, F, N ) (具体表示内容与DFA相同）
4. 对于输入字符串w，如果满足 ∃ s ∈F. R*(s0, w, s)， 那么w是被自动机所接受的。 所有被该自动机接受的字符串就是这个自动机的语言。
5. 定理：如果语言L被一个NFA所接受，那么一定存在一些DFA也接受这一语言L。