《第4章词法分析》.ppt

NFA的确定化 例子 等价的DFA 等价3型文法 G2=(VN,VT,P,S)如下: VN=｛Z,B,M｝R是终止状态没有输出边去掉 VT=｛a,b｝ S=Z P=｛Z→aM|bB|a|b B→aB|bZ|a|b M→bM|b|a｝ 说明: Z→aM|a Z→bB|b 例子: 设有文法如下： G[S]：S→A|bB A→c B→dD D→ε 构造等价自动机。 化简文法：S→c|bB B→dD B→d 例子：确定化和最小化下面自动机 a 1 +- b 3 5 2 4 0 a a a b b b b b a a a b +-0 1 2 1 1 4 2 1 3 4 0 5 3 3 2 5 5 4 由此可知该自动机为确定自动机。 根据状态分为：{0}{1,2,3,4,5} {1,2,3,4,5} {1,5}{2,3,4} ba {2,3,4} {2}{3,4} aba {3,4} {3}{4} a 所以1、5状态等价。 a 1 +- b 3 2 4 0 a a a b b b a b 最小化自动机如下图： 例子：将下图最小化，并描述它所标识的语言。 6 b 2 + a 3 4 1 b c a b b c - 7 - 5 b b d a d 根据状态分为{1,2,3,4,5}和{6,7}两组。 {1,2,3,4,5} {3,4}{1,2,5} b 所以，1、2状态等价，3、4状态等价，6、7状态等价。 {1,2,5} {1,2}{5} bab 最小化结果为： 6 + a 3 5 1 a b b c - d b 例子：设有正则表达式e为: (a|b)*(aa|bb)(a|b)* 构造确定有穷自动机A,使L(A)=L(e) 解：求e的转换系统 S 1 2 (a|b)* Z aa|bb (a|b)* + - 首先，利用求?闭包的方法转化为确定自动机。得出如下表格: S 1 2 b Z a ? ? 4 ? 3 ? b a a b 6 5 b a + - S 1 2 a|b Z aa ? ? 4 ? 3 ? bb a|b - + {3,1,6,4,Z} {3,1,5,2,4,Z} -{3,1,5,4,Z} {3,1,6,2,4,Z} {3,1,5,4,Z} -{3,1,6,4,Z} {3,1,6,2,4,Z} {3,1,5,4,Z} -{3,1,6,2,4,Z} {3,1,6,4,Z} {3,1,5,2,4,Z} -{3,1,5,2,4,Z} {3,1,6,2,4,Z} {3,1,5} {3,1,6} {3,1,6} {3,1,5,2,4,Z} {3,1,5} {3,1,6} {3,1,5} +{S,3,1} b a Move([s,3,1],a)=(3,5) ?-closure(3,5)=[1,3,5] 0 1 2 a 3 b b 4 5 6 b b b b b a a a a a a + - - - - 得到确定自动机如下图: 0 1 2 a 3 b b b b a a a + - 化简后如下图，其中3，4，5，6四个状态等价。 4.4 自动机与正则表达式的关系 定理2.4 对于任一确定自动机A，存在以正则表达式e，使得L(A)=L(e)。反之亦然。 证明：(?)设A为给定确定自动机,则构造相应正则表达式的主要算法如下图。 代之以 1 2 3 1 3 ?? ? ? 1 2 ? ? 代之以 1 2 ?|? 代之以 1 2 3 1 3 ??*? ? ? ? (?)由给定正则表达式β构造相应自动机的主要方法是：首先构造如下扩展转换图 X W ? + - 然后利用下列规则加进节点和边，直至得到ε-自动机为止。 代之以 i k j i j ?? ? ? i j ? ? 代之以 i j ?|? 代之以 i k j i j ?* ? ? ? 在运用上述转换规则前引入一新结点W,并从所有终止结点引出ε边到W结点，并令w为唯一的终止结点。他显然等价于原自动机。 正则式至自动机的转换系统：即一种特殊的状态图，具有唯一的开始状态S和唯一的终止状态Z，没有弧引至S，也没有弧自Z引出，弧可以用ε标记。 S1 S2 + Z1 X - - Z2 + S1 S2 + Z1 X - Z2 S ? ? Z ? ? 例子：将自动机DA转化为正则式 2 3 1 4 a c d f e + - b - 2 3 1 4 a c d f e