有限状态自动机.ppt

(三) 自动机 一、转换图 二、确定有限自动机(DFA) 三、不确定有限自动机(NFA) 四、NFA与DFA的变换 五、?-自动机 六、语法图与自动机 引言 程序设计语言： 。生成系统：文 法 。识别系统：自动机 自动机：具有离散输入输出系统的一种数学模型。 一、转换图（TG） 转换图：字母表?上的有向图。 条件: 1.至少存在一个初始结点 2.存在一些终止结点(可空) 3.在每个边上有字母表?上的符号串(也可以是空串?) 约定:初始结点: ? 终止结点: 一、转换图（TG）(续1) 转换图: 二、确定有限自动机(DFA) 有限自动机(Finite Automata): 二、确定有限自动机(DFA)(续1) 初始状态: 终止状态(接收状态): 后继状态:有限状态机在读入一个字符时,其状态改变为另一状态,则改变后的状态被称为后继状态. 如果有限状态机每次转换后的状态是唯一的则称之为确定有限状态机(DFA);如果转换后的后继状态不是唯一的则称之为不确定有限自动机(NFA); 二、确定有限自动机(DFA)(续2) 状态转换图－描述有限自动机的工作状态 二、确定有限自动机(DFA)(续3) 确定有限状态机:确定有限状态机定义为一个五元组:AD=(S,?,?,K,F) 其中: S:状态的非空集; ?:输入字母表 ?:状态转换函数. S? ??Ｓ的单值映射； ?(Si,a)=Sj, Si, Sj?S K:初始状态;K?S F:终止状态; F?S 二、确定有限自动机(DFA)(续4) 例:AD=(S,?,?,K,F) 其中: S={S0, S1, S2, S3}; ?={a,b,c} K= S0; F={S2, S3}; 转换函数: ?(S0,a)= S1; ?(S1,a)= S0; ?(S1,b)= S2; ?(S1,c)= S3; ?(S2,a)= S2; ?(S2,b)=S1; ?(S3,a)= S1; ?(S3,b)= S3; 二、确定有限自动机(DFA)(续5) 二、确定有限自动机(DFA)(续6) 二、确定有限自动机(DFA)(续7) 三、不确定有限自动机(NFA)(续) 不确定有限自动机所接收的语言 自动机的等价 两个自动机能够接收相同的语言,则称这两个自动机等价. 四、NFA与DFA的变换 1. 实例 NFA与DFA的变换实例 例:AN=(S,?,?’,K,F) 其中: S={S0, S1, S2}; ?={a,b} K= {S0, S1}; F={S2}; 转换函数: ?’(S0,a)= S1; ?’(S0,b)= {S0, S2}; ?’(S1,b)= S2; ?’(S2,b)=S1; NFA与DFA的变换实例(续) NFA与DFA的变换实例(续) NFA与DFA的变换实例(续) NFA与DFA的变换实例(续) 例:AD=(S,?,?,K,F) 其中: S={[S0,S1],[S1],[S0,S2],[S2],[S0,S1,S2]}; ?={a,b} K= {[S0,S1]}; F={[S0,S2],[S2],[S0,S1,S2]}; NFA与DFA的变换实例(续) NFA与DFA的变换实例(续) 五、?-自动机 1、?-自动机:边上有空符号串的自动机. ?FA 2、由?FA构造等价FA。 由?FA构造等价FA步骤： 由?FA构造等价FA步骤： 语法图与自动机 语法图:文法中各个语法成分的图解表示. 方框-----语法成分 圆框-----单词. 例:文 法：G=({标识符,字母,数字}，{字母,数字}，标识符，P) P： 标识符::=字母{字母|数字} 语法图与自动机(续) 语法图与自动机(续) 语法图与自动机(续) 语法图与自动机(续) 语法图与自动机(续) 语法图与自动机(续) * * 1 3 2 ? 01 ? 10 11 00 路:转换图中从某一初始结点到某一终止结点的序列. 对于某一符号串a,在转换图中如存在一条路产生a,则称转换图接收(或识别)符号串a,否则符号串a不能被接收.例如字符串0111为该自动机接收(红色路径表示). 被转换图TG所接收的符号串集合记为L(TG) a b c d d e e f g …….. 控制器 输入带 有限自动机=有限控制器+字符输入带 初始状态 终止状态 S0的后继状态 S0 S2 S1 ? a a b a aa,aaa,aab,aaabb,... 状态转换矩阵: 状态转换图: S0 S2 S1 ? a c b a a b S3 a b ab abaa ac acab acbbbb aa aaa AD所接收的语言:(P57) ac