确定的有限自动机(definite automata, DFA)
1. 定义
确定的有限自动机 是一个五元组：
-
是输入符号的有穷集合；
-
是状态的有限集合；
-
是初始状态；
-
是终止状态集合，
；
-
是
到
2. DFA示意图
处在状态
3. 状态转换图
映射可以由状态变换图描述。
为了明确起见，终止状态用双圈表示，起始状态用有“开始”标记的箭头表示。如:
4. DFA 定义的语言
如果一个句子 使得有限自动机
有
，那么，称句子
被
接受。
由 定义的语言
就是被
接受的句子的全集。即：
-
例子：
链被
接受。
= {含偶数个
和偶数个
的链}
不确定的有限自动机(non-definite automata, NFA)
1. 定义
不确定的有限自动机 是一个五元组：
-
-
-
-
-
的映射。
DFA与NFA
1. DFA与NFA的唯一区别
NFA 与 DFA 的唯一区别是：在 NFA中 是一个状态集合，而在 DFA 中
是一个状态。
- 例子
该自动机为不确定自动机；句子可以被接受。
1. DFA与NFA的关系
设 是一个被 NFA 所接受的句子的集合，则存在一个 DFA它能够接受
。
正则文法与有限自动机的关系
1. 正则文法 
自动机
定理
若是一个正则文法，则存在一个有限自动机
，使得：
。
由
构造
(1) 令，其中，
是一个新增加的非终结符。
(2) 如果在中有产生式
，则
，否则
。
(3) 如果在，
，
，则
。
(4) 如果在, 则
(5) 对于每一个。
1. 自动机 正则文法
定理
若。
由
(1) 令；
(2) 如果，则在
；
(3) 如果，则在
