Chapter 02--形式语言与自动机.pptx

第2章 形式语言与自动机基础;形式语言与自动机基础;2.1 语言和文法;一、字母表和符号串;符号串有关的几个概念;符号串有关的几个概念（续）;连接 符号串?和符号串?的连接??是把符号串?加在符号串?之后得到的符号串 若?=ab，?=cd，则??=abcd，??=cdba。 对任何符号串?来说，都有??=??=? 幂 若?是符号串，?的n次幂?n 定义为：;二、语言;L={A,B, … ,Z,a,b, … ,z}，D={0,1, … ,9} 可以把L和D看作是字母表 可以把L和D看作是语言 语言运算举例：;三、文法及其形式定义;;上下文无关文法及相应的语言;元语言： ::= 表示 “定义为” 或 “由……组成” …… 表示非终结符号 | 表示“或” 算术表达式文法的BNF表示： 表达式 ::= 表达式+项 | 表达式-项 | 项 项 ::= 项*因子 | 项/因子 | 因子 因子 ::= (表达式) | i ;文法书写约定;文法符号 次序靠后的大写字母，如：X、Y、Z 终结符号串 次序靠后的小写字母，如：u、v、…、z 文法符号串 小写的希腊字母，如：?、?、?、? 可以直接用产生式的集合代替四元组来描述文法，第一个产生式的左部符号是文法的开始符号。 ;四、推导和短语;推导; 从文法开始符号E推导出符号串i+i的详细过程;最左推导;句型;对于文法G=(VT,VN,S,?)，假定???是文法G的一个句型，如果存在：;五、分析树及二义性;分析树;;;二义性;文法的二义性和语言的二义性;六、文法的变换;文法二义性的消除;利用“最近最后匹配原则”;句子if E1 then if E2 then S1 else S2的分析树;左递归的消除;例：消除表达式文法中的左递归： E?E+T|T T?T*F|F F?(E)|id 利用消除直接左递归的方法，可以改写为: E?TE? E??+TE? | ? T?FT? T??*FT? | ? F?(E) | id;一般情况：假定关于A的全部产生式是： A?A?1|A?2|…|A?m|?1|?2|…|?n 产生式可以改写为： A??1A?|?2A?|…|?nA? A???1A?|?2 A?|…|?mA?|? ;例如有间接左递归文法： S?Aa|b A?Ac|Sd|? ;算法：消除左递归;为含有?-产生式的文法G=(VT,VN,S,?) 构造不含?-产生式的文法G?=(VT?,VN?,S,??)的方法;示例：消除下面文法中的左递归 S?Aa|b A?Ac|Sd|?;提取左公因子;示例：映射程序设计语言中IF语句的文法 stmt? if expr then stmt | if expr then stmt else stmt | a expr?b;2.2 有限自动机;有限自动机;一、确定的有限自动机（DFA）;利用状态转换图，识别符号串;确定的有限自动机的定义;示例：有 DFA M=({0,1},{A,B,C,S,f},S,{f},?) 其中 ?(S,0)=B ?(A,0)=f ?(B,0)=C ?(C,0)=f ?(S,1)=A ?(A,1)=C ?(B,1)=f ?(C,1)=f;DFA M所识别的语言;二、非确定的有限自动机（NFA）;NFA的状态转换图及识别的语言;NFA示例： 设有 NFA M=({a,b},{0,1,2,3},0,{3},? ) 其中 ?(0,a)={0,1} ?(0,b)={0} ?(1,b)={2} ?(2,b)={3};定理：对任何一个NFA M，都存在一个与之等价的 DFA D，即L(M)=L(D)。;;子集构造法：构造与NFA M等价的DFA D;三、具有?-转移的非确定有限自动机;示例： 有NFA M=({a,b},{0,1,2,3,4},0,{2,4},? )  其中 ?(0,?)={1,3} ?(1,a)={1,2} ?(3,b)={3,4};F?=;;推论：对于任何一个具有?-转移的NFA M，都存在 一个与之等价的DFA D，即L(M)=L(D)。;算法：计算?_closure(T);算法：为NFA构造等价的DFA;示例：构造与下面的NFA