编译原理 —— 有穷自动机（FA）
有穷自动机的定义
系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。当前状态+当前输入=后继行为
FA模型
FA转换图
- 结点：FA的状态
- 初始状态（开始状态）：只有一个，由start箭头指向
- 终止状态（接收状态）：可以有多个，用双圈表示
- 带标记的有向边：如果对于输入a，存在一个从状态p到状态q的转换，就在p、q之间画一条有向边，并标记上a。（如图中0到1）
FA定义的语言
- 给定输入串x，如果存在一个对应于串x的从初始状态到某个终止状态的转换序列，则称串x被该FA接收由
- 一个有穷自动机M接收的所有串构成的集合称为是该FA定义（或接收）的语言，记为L（M）
如上图中， L（M）=所有以abb结尾的字母表{a，b}上的串的集合（包括abb）
最长子串匹配原则
- 当输入串的多个前缀与一个或多个模式匹配时，总是选择最长的前缀进行匹配
- 在到达某个终态之后，只要输入带上还有符号，DFA就继续前进，以便寻找尽可能长的匹配
确定的有穷自动机（DFA）
非确定的有穷自动机 (NFA)
带有ε边的NFA
带有和不带有“ε边"的NFA的等价性
当状态A收到0，0∈{0}，可以进入状态A，0∈{0,1}，可以进入状态B，0∈{0,1,2}，可以进入状态C
DFA和NFA的等价性
- 对任何非确定的有穷自动机N，存在定义同一语言的确定的有穷自动机D
- 对任何确定的有穷自动机D，存在定义同一语言的非确定的有穷自动机N
都可以识别以abb结尾的串，NFA更直观，DFA更容易实现
参考地址
https://www.icourse163.org/learn/HIT-1002123007?tid=1003246005#/learn/announce