首页 > 代码库 > 有穷自动机
有穷自动机
什么是自动机？？
自动机是一种能进行运算并能实现自我控制的装置。一台存储有程序的传统计算机，在有合适电源的条件下不仅具有进行运算的能力，而且具有自我控制的能力，所以，计算机是一部自动机。自动机是描述符号串处理的强有力的工具，因而，自动机成为研究词法分析程序的重要基础。有穷自动机（FA）分为确定有穷自动机（DFA）和非确定有穷自动机（NFA）。有穷自动机用来识别符号串的语法成分是否属于特定语言。
1，DFA（确定有穷自动机）
一个确定有穷自动机DFA是由一个五元组来定义 DFA = ( Q，∑，t，q0，F )。
Q 是非空有穷的状态集，其中的每个元素称为一个状态。
∑ 是非空有穷的输入字母表，其中的每个元素称为一个输入符号。
t 是一个单值映射 Q × ∑ → Q ，也称为状态转换函数；例如，t（q，x）→ q` 是指当前状态 q 扫描到输入符号x时，将转到下一状态q`，q` 称为 q 的唯一一个后继状态。
q0 是的开始状态且 q0∈Q，DFA的开始状态唯一。
F 是非空有穷的终止状态集且 F Q ；F 状态集合是 Q 状态集合的子集，至少包含一个终止状态。
2，DFA的确定性
当前状态面临下一个输入符号时唯一地确定了下一个当前状态。
3，NFA（非确定有穷自动机）
一个非确定有穷自动机NFA也是由一个五元组来定义 NFA = ( Q，∑，t，Q0，F )。
Q 是非空有穷的状态集，其中的每个元素称为一个状态。
∑ 是非空有穷的输入字母表，其中的每个元素称为一个输入符号。
t 是一个多值映射 Q × ∑ → Q ，也称为状态转换函数；例如，t（q，x）→ { q1，q2 } 是指当前状态 q 扫描到输入符号x时，将转到的下一状态为 q1或 q2，这时当前 状态 q 就有 q1 和 q2 两个后继状态（一对多的关系）。
Q0 是非空有穷的开始状态集且 Q0 Q，NFA的开始状态可以有多个。
F 是非空有穷的终止状态集且 F Q ；F 状态集合是 Q 状态集合的子集，至少包含一个终止状态。
4，NFA的非确定性
当前状态面临下一个输入符号时不能唯一地确定下一个当前状态。
5，DFA和NFA的区别
1，DFA 只有一个开始状态，而 NFA 有一个开始状态集；
2，DFA 的状态转换函数是一个单值映射，而 NFA 是一个多值映射；
3，DFA 不能进行空移，而 NFA 能进行空移；
6，描述有穷自动机的方法
1，状态转换表
2，状态转换图
3，映射的形式描述
for example：确定有穷自动机 A，对于输入符号 a，b，若其当前状态为q0，则分别转入状态q1，q3；若当前状态为q1，则分别转入状态q0，q2；若当前状态为q2，则分别转入状态q3，q1；若当前状态为q3，则分别转入状态q2，q0。
用状态转换表描述自动机 A：
用状态转换图描述自动机 A：
PS：如上图，状态 q0 用双圆圈标记，表明它是终止状态；同时，用一个箭头标记，表明它是开始状态。这就是说，状态 q0 既是开始状态又是终止状态。由状态转换图可以直观地看到状态间的转换。如状态 q0 经输入字母 a 可转换成状态 q1。一个状态转换图实际上就是一个有穷自动机，因为状态转换图中完全包括了有穷自动机的五个部分。状态转换图中，如果有 m 个状态，n 个输入字符，那么这个状态转换图中有 m 个结点，每个结点上最多有 n 条弧射出。
用映射的形式描述描述自动机 A：
t（q0，a） = q1 t（q0，b） = q3
t（q1，a） = q0 t（q1，b） = q2
t（q2，a） = q3 t（q2，b） = q1
t（q3，a） = q2 t（q3，b） = q0
7，非确定有穷自动机的状态转换图
PS：由上图可知，映射 t（q0，x） = { q1，q2 }，表示如果当前状态是 q0，当遇到输入字符 x 时，将转换为 q1 或 q2 状态，显然是不确定的。所以状态结点 q0 到状态结点 q1 和 q2 的弧上，均标记输入字符x。
本文出自 “珞辰的博客” 博客，谢绝转载！
有穷自动机