1、第 1 页第 2 章 形式语言与自动机基础2.1 文法和语言2.2 有限自动机2.3 正规式与有限自动机Ch2 形式语言自动机理论基础 2.2 自动机基础第 2 页第 2 章 形式语言与自动机基础2.2 有限自动机基础2.2.1 确定的有限状态自动机 (DFA)2.2.2 非确定的有限状态自动机 (NFA)2.2.3 NFA确定化2.2.4 DFA化简 Ch2 形式语言自动机理论基础 2.2 自动机基础第 3 页 定义 2.24一个确定的有限自动机 M ( DFA M)是一个五元组M =（ Q, , f, q0, Z）Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的 FA
2、（ DFA）一. 确定的有限自动机（ DFA）二 . ( DFA： Deterministic Finite Automaton )其中：Q： 状态的有限集合，每个元素 qi (qi Q) 称为一个状态。第 4 页： 输入字符的有限集合 (或有穷字母表 )。每个元素是一个输入字符。Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的 FA（ DFA）q0： M的唯一初态（也称开始状态）， q0Q。f： 状态转换函数：从 QQ的映射。例如 , f（ p,a） =q, q、 pQ, a。 表示了状态p在输入字符 a之后转入状态 q。 q也称为 p的后继状态。Z： M的终态集（或接
3、受状态） ZQ。第 5 页Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的 FA（ DFA）二 . DFA的等价表示 DFA形式定义 状态转换图 状态转换表例 2.20: DFA M = （ 0,1,2,3, a,b, f , 0 , 3）f（ 0,a） =1 f（ 0,b） =2f（ 1,a） =3 f（ 1,b） =2f（ 2,a） =1 f（ 2,b） =3f（ 3,a） =3 f（ 3,b） =3Q q0 Zf第 6 页Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的 FA（ DFA） 状态转换图表示DFA 状态图Q 状态结点 弧上标记 (边
4、权值 )f 带权值的有向边q0Z q0Z第 7 页Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的 FA（ DFA）0 12 3aabb ab 状态转换图表示 DFA M =(0,1,2,3, a,b, f , 0 , 3）f（ 0,a） =1 f（ 0,b） =2f（ 1,a） =3 f（ 1,b） =2f（ 2,a） =1 f（ 2,b） =3f（ 3,a） =3 f（ 3,b） =3ab第 8 页Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的 FA（ DFA）二 . DFA的等价表示 DFA形式定义 状态转换图 状态转换表例 2.20: DF
5、A M = （ 0,1,2,3, a,b, f , 0 , 3）f（ 0,a） =1 f（ 0,b） =2f（ 1,a） =3 f（ 1,b） =2f（ 2,a） =1 f（ 2,b） =3f（ 3,a） =3 f（ 3,b） =3Q q0 Zf第 9 页Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的 FA（ DFA） 状态转换表表示a b0 1 2 1 3 22 1 2 3* 3 3fQq0ZDFA M =(0,1,2,3,a,b, f , 0 , 3）f（ 0,a） =1 f（ 0,b） =2f（ 1,a） =3 f（ 1,b） =2f（ 2,a） =1 f（ 2,b） =3f（ 3,a） =3 f（ 3,b） =3第 10 页Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的 FA（ DFA）三 . DFA的识别机制 如果存在 Q中的状态序列 p0， p1， ， pn， 满足下列条件：1) p0 q02) f（ pi， wi 1） pi 1， i 0， 1， ， n 13) pnZ则 M接受（识别） 。确定的有限自动机 M=（ Q, , f, q0, Z） 接受或识别 字母表 上的 字符串 w1w2 wn 的意义：
