1、形式语言与自动机形式语言与自动机Formal Languages and Automata Theory教师教师：胡：胡春明、赵永春明、赵永望、邓婷望、邓婷第三章第三章 有穷自动机有穷自动机第三章第三章 有穷状态自动机有穷状态自动机一、有穷状态自动机一、有穷状态自动机 FA FA 定义与表示定义与表示二、确定的有穷自动机二、确定的有穷自动机 DFADFA三、非确定的有穷自动机三、非确定的有穷自动机 NFANFA四、四、DFA DFA 和和 NFA NFA 的等价性的等价性五、带空移动的有穷自动机五、带空移动的有穷自动机- NFA- NFA六、六、FA FA 是正则语言的识别器是正则语言的识别器
2、 七、七、FA FA 的变形的变形 - - 带输出的带输出的 FAFA第第一一次课次课第二第二次课次课例例 3：求接受语言求接受语言 L（M）= x | x 0,1 *，且，且 x 含有子串含有子串 00 或或 11 的的 FA。三、非确定有穷自动机三、非确定有穷自动机 NFANFA例例 3：求接受语言求接受语言 L（M）= x | x 0,1 *，且，且 x 含有子串含有子串 00 或或 11 的的 FA。状态表状态表状态图状态图三、非确定有穷自动机三、非确定有穷自动机 NFANFA3、此时的、此时的N FA 程序应视为程序应视为拥有拥有“智能智能” ，亦即，在一给定，亦即，在一给定状态下，
3、它可根据当前从输入字符串读入的字符自动到状态下，它可根据当前从输入字符串读入的字符自动到( q, a ) 的转移状态的转移状态集合集合中选择进入一个正确的状态。中选择进入一个正确的状态。非确定有穷自动机非确定有穷自动机 NFANFA非确定有穷自动机非确定有穷自动机 NFANFA几个相关的基本概念：几个相关的基本概念：1、引入基于字符串的状态转移函数、引入基于字符串的状态转移函数；2、 NFA 接受句子及语言的条件接受句子及语言的条件3、两个、两个 NFA 的等价的等价非确定有穷自动机非确定有穷自动机 NFANFA非确定有穷自动机非确定有穷自动机 NFANFA非确定有穷自动机非确定有穷自动机 N
4、FANFA定义定义 3-8 的补充：的补充： 状态转移函数状态转移函数扩展为扩展为 对于任意的对于任意的 q Q, w , a ，有：，有：( q, wa ) = ( ( q, w ), a ) =( ( q, a1 a2 a3 an），）， a ) = ( ( ( q, a1 ), a2 ), an ), a ) 非确定有穷自动机非确定有穷自动机 NFANFA说明说明 1 1：NFA NFA 从状态从状态 q q 出发处理字符串出发处理字符串 wa 状态转移过程：状态转移过程：说明说明 2：由于由于 Q是是 Q* 的真子集；对于任意的的真子集；对于任意的 q Q，a ，有，有 ( q，a )
5、 = ( q，a ) 是单位元素是单位元素 = pr ( q，)，使得，使得 p ( r, a ) 由定义第由定义第 2 条条 = pr q ，使得，使得 p ( r, a ) 由定义第由定义第 1 条条 = pp ( q，a ) q 是是 r 的唯一值的唯一值 =( q，a ) 非确定有穷自动机非确定有穷自动机 NFANFA可见，状态转移函数可见，状态转移函数 可涵盖可涵盖 描述函数，故应用中不必区分描述函数，故应用中不必区分和和 ，通常一般性地用通常一般性地用代替代替 。说明说明 3 3：为了叙述方便，为了叙述方便，还可还可进一步扩展进一步扩展 NFA NFA 状态转移状态转移函数函数的的
6、定义域：定义域：q q非确定有穷自动机非确定有穷自动机 NFANFA函数函数 : ( Q） * ( Q ) = 2Q 定义如下定义如下: (1) ( q, ) = q (2) ( q, wa ) = pr ( q，w )，使得，使得 p ( r, a ) q Q3) ( P，w ) = ( q，w ) P Q4) ( q , w ) = ( q, w ) = ( q, w ) 非确定有穷自动机非确定有穷自动机 NFANFA状态转移函数状态转移函数 定义内涵小结：定义内涵小结： qqqP几个相关的基本概念：几个相关的基本概念：1、基于字符串的状态转移函数、基于字符串的状态转移函数；2、 NFA
7、接受句子及语言的条件接受句子及语言的条件3、两个、两个 NFA 的等价的等价非确定有穷自动机非确定有穷自动机 NFANFA非确定有穷自动机非确定有穷自动机 NFANFA几个相关的基本概念：几个相关的基本概念：1、基于字符串的状态转移函数、基于字符串的状态转移函数；2、 NFA 接受句子及语言条件接受句子及语言条件3、两个、两个 NFA 的等价的等价非确定有穷自动机非确定有穷自动机 NFANFA定义定义 3-10：设设 M1，M2 是是 FA。如果。如果 L（M1）= L（M2），则），则称称 M1 与与 M2 等价。等价。非确定有穷自动机非确定有穷自动机 NFANFA非确定有穷自动机非确定有穷
8、自动机 NFANFA文法、自动机部分作业文法、自动机部分作业v1 1、DFA、NFA、- NFA ：教材第三章习题教材第三章习题 2 2（3,5,7,113,5,7,11），10（2,5），11(2), 14(5), 15(2)（ 第二版第二版P126 P128，第三版，第三版P101-107 ）教材第三章习题教材第三章习题 20, 22(2)（ P129 ）下周内交下周内交课代表，交新主楼课代表，交新主楼G1119DFA 与与 NFA 等价：等价：1 1、二者均是、二者均是正则语言正则语言识别模型，用于识别正则语言。识别模型，用于识别正则语言。2 2、对于任意给定的、对于任意给定的 DFAD
9、FA，肯定存在一个，肯定存在一个 NFA NFA 与之等价。与之等价。3 3、需证：对于任意给定的、需证：对于任意给定的 NFANFA，存在一个，存在一个 DFA DFA 与之等价。与之等价。四、四、DFA 与与 NFA 的等价性的等价性证明思路：证明思路： 1、构造与、构造与 NFA M1 = 相应的相应的 DFA M2 = 2、证明对任意输入字符串、证明对任意输入字符串 x，有，有 2 ( q0, x ) = 1 ( q0, x ); 3、证明、证明 L（M1）= L（M2）成立。）成立。DFA 与与 NFA 的等价性的等价性定理定理 3-1： 对任一对任一 NFA，都存在一个，都存在一个
10、 DFA 与其等价。与其等价。 1、M1 的初始状态的初始状态 q0 对应到对应到 M2 的的 q0 = q0 ；2、如果、如果 NFA M1 当前的一个状态组当前的一个状态组 q1, q2, , qn ，读入字符，读入字符 a 后，后， 进入进入状态组状态组 p1, p2, , pm ，则相应的，则相应的 DFA 在综合状态在综合状态 q1, q2, , qn 下，读入下，读入字符字符 a 后，进入新的综合状态后，进入新的综合状态 p1, p2, , pm 。3、如果、如果 NFA 接受某输入串接受某输入串 x，满足，满足 (1 ( q0, x ) F1 )，则，则 NFA M1终止终止状态
11、组状态组 p1, p2, , pn 相应的状态相应的状态 p1, p2, , pn 应为应为 DFA 的终止状态，的终止状态，即有，即有， p1, p2, , pn F2。 NFA/DFA 模型区别：模型区别： 2：给定给定 NFA M1 = ， 构造构造 DFA M2 = ，并在二者之间建立对应关系如下。，并在二者之间建立对应关系如下。DFA 与与 NFA 的等价性的等价性1：对于对于 NFA 任一时刻同时转向多个状态任一时刻同时转向多个状态 p1, p2, , pm ； DFA 可将这些状可将这些状态汇集在一起，将其态汇集在一起，将其“总效果总效果”视为自己的一个视为自己的一个“综合状态综
12、合状态” p1, p2, , pm 形式化证明形式化证明 - 步骤步骤 1：构造：构造设设 NFA M1= ，取，取 DFA M2 = ，其中，其中， 1）Q2 = ( Q1 ) ； 2）F2 = p1, p2, , pm | p1, p2, , pm Q1 且且 p1, p2, , pm F1 ； 3）对）对 q1, q2, , qn Q1，a ， 2（ q1, q2, , qn ）, a）= p1, p2, , pm 1（ q1, q2, , qn ）, a）= p1, p2, , pm DFA 与与 NFA 的等价性的等价性2、设、设 | x | = n 时，结论成立，求证时，结论成立，
13、求证 | x | = n + 1 时，结论也成立。时，结论也成立。 设设 x = w a，其中，其中， | w | = n， a 。 由由 NFA 定义，定义，1 ( q0, w a ) = 1 ( 1 ( q0, w ), a ) = 1（ q1, q2, , qn , a ） = p1, p2, , pm 由归纳假设由归纳假设 1 ( q0, w ) = q1, q2, , qn 2 ( q0 , w ) = q1, q2, , qn 由由2 构造定义构造定义 2（ q1, q2, , qn , a）= p1, p2, , pm 1（ q1, q2, , qn , a）= p1, p2,
14、, pm 所以有，所以有， 2 ( q0 , w a ) = 2 ( 2 ( q0 , w ), a ) = 2（ q1, q2, , qn ，a ）= p1, p2, , pm 结论成立；得证。结论成立；得证。 步骤步骤 2：判断状态转移：判断状态转移设设 x *，施归纳于，施归纳于 | x | ： 1、当、当 x =, 有有1 ( q0 , ) = q0 ，2 ( q0 , ) = q0 ，结论成立，结论成立 ；DFA 与与 NFA 的等价性的等价性步骤步骤 3：判断对字符串的接受条件：判断对字符串的接受条件设设 x L（M1），）， 有有1 ( q0, x ) = p1, p2, , p
15、m 并且并且 1 ( q0, x ) F1 亦即，亦即， p1, p2, , pm F1 由由 M2 中中 F2 定义：定义： p1, p2, , pm F2证明步骤证明步骤 2 可知可知: 2 ( q0, x ) = p1, p2, , pm ，故有，故有 x L ( M2)所以，有：所以，有： L（M1） L（M2）反之可推得：反之可推得： L（M2） L（M1）从而，有从而，有 L（M1）= L（M2） 综上综上1) 2) 3), 定理得证定理得证DFA 与与 NFA 的等价性的等价性DFA 与与 NFA 的等价性的等价性构造与构造与 NFA 等价的等价的 DFA 算法：算法：a）将）将
16、 NFA 的始态集的始态集 q0 作为作为 DFA 的始态的始态 q0 加入到状态表的状态列加入到状态表的状态列b）如果状态表的状态列中还有未被处理的状态，则任选其中的一个状态）如果状态表的状态列中还有未被处理的状态，则任选其中的一个状态 q1, q2, , qn ，对所有输入字符，对所有输入字符 a ，计算，计算2（ q1, q2, , qn , a）的）的转移状态转移状态 p1, p2, , pm ，并将其填入状态表输入字符列对应的表项中，并将其填入状态表输入字符列对应的表项中c）如果计算）如果计算2（ q1, q2, , qn , a）新获得的转移状态）新获得的转移状态 p1, p2,
17、, pm 从从未在状态列中出现过，则将其填入状态列中；未在状态列中出现过，则将其填入状态列中；d）重复执行）重复执行 b) 和和 c)，直到状态表的状态列中状态全部处理完毕为止。，直到状态表的状态列中状态全部处理完毕为止。状状 态态 表表 例例状态列状态列输入字符列输入字符列01q0 q0, q1 q0, q2 DFA 与与 NFA 的等价性的等价性例：构造如图所示的例：构造如图所示的 NFA 等价的等价的 DFA。状态说明状态说明DFA 状态列状态列输入字符输入字符01开始状态开始状态 Pq0 q0, q1 q0, q2 中间状态中间状态 P q0, q1 q0, q1, q3 q0, q2
18、 中间状态中间状态 P q0, q2 q0, q1 q0, q2, q3 终止状态终止状态 P q0, q1, q3 q0, q1, q3 q0, q2, q3 终止状态终止状态 P q0, q2, q3 q0, q1, q3 q0, q2, q3 按算法建立状态表按算法建立状态表：DFA 与与 NFA 的等价性的等价性状态说明状态说明DFA 状态列状态列输入字符输入字符01开始状态开始状态 Pq0 q0, q1 q0, q2 中间状态中间状态 P q0, q1 q0, q1, q3 q0, q2 中间状态中间状态 P q0, q2 q0, q1 q0, q2, q3 终止状态终止状态 P q
19、0, q1, q3 q0, q1, q3 q0, q2, q3 终止状态终止状态 P q0, q2, q3 q0, q1, q3 q0, q2, q3 DFA 与与 NFA 的等价性的等价性习题：习题：p.128. 11 给定给定NFA构造等价的构造等价的DFA小结：小结：1、非、非确定型确定型有穷自动机有穷自动机 NFA 的一般概念：的一般概念： 自动机定义自动机定义 五元组：五元组： M = ； NFA 的状态转移函数的状态转移函数 可以不唯一；可以不唯一； NFA 接受语言条件；接受语言条件；NFA 的等价性。的等价性。2、NFA 与与 DFA 等价性的构造性证明方法：等价性的构造性证明
20、方法： 1）、给定）、给定 NFA，构造与其相关的，构造与其相关的 DFA M2 = 2）、证明对于同一输入字符串，二者状态转移相同；）、证明对于同一输入字符串，二者状态转移相同； 3）、）、证明二者识别的语言相同。证明二者识别的语言相同。3、由、由 NFA 构造构造 DFA 算法及其应用算法及其应用第三章第三章 有穷状态自动机有穷状态自动机一、有穷状态自动机一、有穷状态自动机 FA FA 定义与表示定义与表示二、确定的有穷自动机二、确定的有穷自动机 DFADFA三、非确定的有穷自动机三、非确定的有穷自动机 NFANFA四、四、DFA DFA 和和 NFA NFA 的等价性的等价性五、带空移动
21、的有穷自动机五、带空移动的有穷自动机- NFA- NFA六、六、FA FA 是正则语言的识别器是正则语言的识别器 七、七、FA FA 的变形的变形 - - 带输出的带输出的 FAFA五、带空移动的有穷自动机五、带空移动的有穷自动机- NFA五、带空移动的有穷自动机五、带空移动的有穷自动机- NFA定义定义 3-10： 带空移动的不确定有穷状态自动机带空移动的不确定有穷状态自动机- NFA M 是一个五元组：是一个五元组： M =（Q，q0，F ），其中，），其中，Q，q0，F 意义同意义同 FA；转移函数转移函数： Q ( ) 2Q ：于：于 q Q, a ， 1、( q, a ) = p1,
22、 p2, , pm 表示表示 M 在状态在状态 q 下，读入字符下，读入字符 a, 选择地选择地将状态变为将状态变为 p1, p2, , 或或 pm，并将读头向右移动一个方格，并将读头向右移动一个方格， 指向下一指向下一个输入字符，个输入字符， 称称 M 在状态在状态 q 做一个非空移动。做一个非空移动。2、( q, ) = p1, p2, , pm 表示表示 M 在状态在状态 q 下，不读入任何字符下，不读入任何字符, 可可选择地将状态变为选择地将状态变为 p1, p2, 或或 pm，称，称 M 在状态在状态 q 做一个空移动。做一个空移动。几个相关的基本概念：几个相关的基本概念：1、引入基
23、于字符串的状态转移函数、引入基于字符串的状态转移函数2、 NFA 接受句子及语言条件接受句子及语言条件带空移动的有穷自动机带空移动的有穷自动机- NFA 状态转移函数状态转移函数的推广：的推广： ( q, a ) ( q, w ) 定义定义 - NFM 的目的是为了用来识别语言的句子；的目的是为了用来识别语言的句子；因此，需要将状态转移函数因此，需要将状态转移函数的定义域从的定义域从 Q 推广推广到到Q*。带空移动的有穷自动机带空移动的有穷自动机- NFA带空移动的有穷自动机带空移动的有穷自动机- NFA定义定义 3-10 的补充：的补充：对于任意对于任意 P Q, q Q, a , w *,
24、 定义概念：定义概念： （1）- CLOSURE ( q ) = p | q 到到 p 有标记为有标记为的通路的通路 ； （2）- CLOSURE ( P ) = P Q : 扩展的定义域扩展的定义域( )p PCLOSURE p这里，这里，- CLOSURE ( q ) 是满足以下条件的最小集合，满足，是满足以下条件的最小集合，满足，1） ( q, ) - CLOSURE ( q )； 2）若）若 q - CLOSURE ( q ), 则则( q, ) - CLOSURE ( q )。带空移动的有穷自动机带空移动的有穷自动机- NFA定义定义 3-10 的补充：的补充：转移函数转移函数扩展为
25、扩展为 的递归定义：的递归定义： ( 1 ) ( q, ) = - CLOSURE ( q )； q 通过可达的状态集合 ( 2 ) ( q, wa ) =- CLOSURE ( P ) ， 其中， P = pr ( q，w )，使得，使得 p ( r, a ) = =( )p PCLOSURE p)( ,( , )rqr a一个移动）一个移动）多个移动）多个移动）（基于字符的（基于字符的（基于字符串的（基于字符串的带空移动的带空移动的- NFA注：在注：在- NFA 中，中， ( q, ) ( q, )； ( q, a ) ( q, a ) 。几个相关的基本概念：几个相关的基本概念：1、基于
26、字符串的状态转移函数、基于字符串的状态转移函数2、- NFA 接受句子及语言条件接受句子及语言条件带空移动的有穷自动机带空移动的有穷自动机- NFA定义定义 3-11： 设设 M = 是一是一- NFA。对于。对于 x *，如果，如果 ( q0, x ) F ，则称，则称 x 被被 M 识别识别 ( 或接受，或表现或接受，或表现 )；如果；如果( q0, x ) F = ，则称，则称 M 不接受不接受 x 。 L（M）= x | x *且且( q0, x ) F 称为由称为由 M 接受（识别）的语言。接受（识别）的语言。带空移动的有穷自动机带空移动的有穷自动机- NFA带空移动的有穷自动机带空
27、移动的有穷自动机- NFA定理定理 3-2： - NFA M1 与与 NFA M2 等价。等价。 证明思路分析：证明思路分析：1、由于、由于 NFA M2 是是- NFA M1的特例，显然有：的特例，显然有： L ( M2 ) = L ( M1 )2、对于、对于- NFA M1，需需构造构造 NFA M2，并，并证明：证明： L ( M1 ) = L ( M2 ) 构造构造 NFA 的关键：的关键：给定给定- NFA M1 ，构造构造 NFA M2 模拟模拟 M1，亦即，用，亦即，用 NFA 的非空移动的非空移动去代替去代替 - NFA 中包含若干空移动以及一个相应的非空的中包含若干空移动以及
28、一个相应的非空的移动组合移动组合。带空移动的有穷自动机带空移动的有穷自动机- NFA设设二者的二者的 Q、q0 分别对应相同，构造不同于分别对应相同，构造不同于 M1 的的 NFA M2 的终的终止状态止状态 F2 和状态转移函数和状态转移函数2 如下：如下： F q0 如果如果 F - CLOSURE ( q0 ) （1）F2 = F 如果如果 F - CLOSURE ( q0 ) = （2）对于）对于 ( q, a ) Q，定义，定义 2 ( q, a ) = 1 ( q, a ) 1、构造、构造 NFA：设有：设有- NFA M1 = （Q，1，q0，F ），构造与之），构造与之等价的等
29、价的 NFA M2 = （Q，2，q0，F2 ）如下。）如下。带空移动的有穷自动机带空移动的有穷自动机- NFA2、构造的正确性证明：、构造的正确性证明： 1 1、 对于输入的任意非空字符串，对于输入的任意非空字符串，NFA 与与- NFA识别的识别的字符串相同，亦字符串相同，亦即，可证明在非空字符串中引入空移动不会影响被识别句子本身：即，可证明在非空字符串中引入空移动不会影响被识别句子本身： i) 证证 NFA 与与- NFA 转移状态相同转移状态相同 ： x +, 2 ( q0, x ) = 1 ( q0, x ) ii) 证证 NFA 与与- NFA 同时转入终态（或非终态）同时转入终态
30、（或非终态）- x +, x L( M2 ) x L( M1 ) , 亦即亦即 2 ( q0, x ) F2 1 ( q0, x ) F 2、对于输入的空字符串、对于输入的空字符串，二者识别相同：，二者识别相同： L( M1 ) L( M2 ) 。带空移动带空移动- NFA证明证明 1）： 1、当、当 | x | = 1, 由由2 的构造定义，结论成立的构造定义，结论成立 ；2、设、设 | x | = n 时，结论成立，求证时，结论成立，求证 | x | = n + 1 时，结论也成立。时，结论也成立。 设设 x = w a，其中，其中， | w | = n， a 。 由由 NFA 定义，定义
31、，2 ( q0, x ) = 2 ( q0, w a ) = 2 ( 2 ( q0, w ), a ) = 2 ( 1 ( q0, w ), a)- NFA 读串转移归纳读串转移归纳 = 2 2 构造定义构造定义 = - NFA 读串定义读串定义 = = = =结论成立结论成立 102 (,)(,)qqq a101 (,) (,)qqq a101(|,)CLOSUREpqqwpq a 使得101 (,)( , )qqwCLOSUREq a10,qwa10,qx带空移动带空移动- NFA证明证明 2）：）： x*，x L( M2 ) x L( M1 ) i) 设设 x =，由，由 NFA 的转移
32、函数扩展定义的转移函数扩展定义 2 ( q0, ）= q0 有：有： L( M2 ) 2 ( q0, ) F2 是是语句语句 q0 F2 q0 F F - CLOSURE ( q0 ) F2 定义定义 q0 状态状态 F 1 ( q0, ) - NFA 读读闭包定义闭包定义 L( M1 ) 是是- NFA M1 语句语句带空移动带空移动- NFA证明证明 2）：）： x+，x L( M2 ) x L( M1 ) ii) 设设 |x| 1，由，由 NFA 的转移函数扩展定义的转移函数扩展定义 2 ( q0, x ）有：）有：x L( M2 ) 2 ( q0, x ) F2 x 是是 M2 语句语
33、句 2 ( q0, x ) (F2 = F ) F2 定义定义 |x| 1 1 ( q0, x ) F 由由2 的构造证明的构造证明 1) x L( M1 ) x 是是 M1 语句语句带空移动的有穷自动机带空移动的有穷自动机- NFA 1例：例：给定识别给定识别 L (M1) = 0n1m2k | n, m, k 0 的的- NFA，求等价的，求等价的 NFA M2给定的给定的 M1：构造的构造的 M2：带空移动的有穷自动机带空移动的有穷自动机- NFA例例：p.129, 15. 给定给定- NFA，构造与之等价的，构造与之等价的NFA第三章第三章 有穷状态自动机有穷状态自动机一、有穷状态自动
34、机一、有穷状态自动机 FA FA 定义与表示定义与表示二、确定的有穷自动机二、确定的有穷自动机 DFADFA三、非确定的有穷自动机三、非确定的有穷自动机 NFANFA四、四、DFA DFA 和和 NFA NFA 的等价性的等价性五、带空移动的有穷自动机五、带空移动的有穷自动机- NFA- NFA六、六、FA FA 是正则语言的识别器是正则语言的识别器七、七、FA FA 的变形的变形 - - 带输出的带输出的 FAFA回顾：正则文法和正则语言回顾：正则文法和正则语言定义定义2.62.6 (乔姆斯基文法体系乔姆斯基文法体系) ：设设 G= ( V, T, P, S )，P= ， ( V T )+，
35、 ( V T )*1）G 叫作叫作 0 型文法，或短语结构文法（型文法，或短语结构文法（PSG）；对应地，）；对应地，L（G）叫）叫 0 型语言或型语言或 短语短语结构语言（结构语言（PSL）、递归可枚举集。）、递归可枚举集。2）如果对于）如果对于 P，均有，均有 | | | |，则称，则称 G 为为 1 型文法，或上下文有关文法（型文法，或上下文有关文法（CSG）；）；对应地，对应地，L（G）叫）叫 1 型语言或型语言或上下文有关上下文有关语言语言 ( CSL ).3）如果对于）如果对于 P，均有，均有 | | | |，并且，并且 V，则称，则称 G 为为 2 型文法，或上型文法，或上下文无
36、关文法（下文无关文法（CFG）；）；对应地，对应地，L（G）叫）叫 2 型语言或型语言或上下文无关上下文无关语言（语言（CFL）。）。4）如果对于）如果对于 P， 均具有以下形式：均具有以下形式：A ， A B； 其其中，中，A, B V， T+，则称，则称 G 为为 3 型文法，或正则文法（型文法，或正则文法（RG）；）；对应地，对应地，L（G）叫）叫 3 型语言或型语言或正则正则语言（语言（RL）。）。其它：其它： “空语句空语句 ”2、相关定理的两点结论：（相关定理的两点结论：（ 证明见证明见 P80 - P82） i) 在语言中增加或者去掉空语句在语言中增加或者去掉空语句，不会影响原来
37、语言的类型，如，不会影响原来语言的类型，如语言原来是语言原来是RL，增加或减去，增加或减去后仍然是后仍然是 RL； ii) 需要时，语言中可增加需要时，语言中可增加语句，同时，产生式中增加语句，同时，产生式中增加 A 。1、正常情况下，各类语言均没有空语句、正常情况下，各类语言均没有空语句 。由于引入空语句对语言本由于引入空语句对语言本身没有影响；并且，为了便于处理问题，有时需要在语言中引入空语身没有影响；并且，为了便于处理问题，有时需要在语言中引入空语句。例如，句。例如，构造带空移动的自动机构造带空移动的自动机-NFA 。六、六、FA FA 是正则语言的识别器是正则语言的识别器1、已知：任一
38、正则语言、已知：任一正则语言 L 都存在一正则文法都存在一正则文法 G = ( V, T, P, S )，使得，使得 L = L（G）。）。2、 已知：已知：G 为右线性文法，如果对于为右线性文法，如果对于 （ ） P 均有以下均有以下 形式：形式：A ； A B； 其中，其中，A，B V， T+。3、 已知：已知：G 为左线性文法，如果对于为左线性文法，如果对于 （ ） P 均具有以下均具有以下 形式：形式：A ； A B； 其中，其中，A，B V， T+。4、证明、证明 FA 可识别右可识别右 ( 左左 ) 线性文法派生的正则语言，亦即，线性文法派生的正则语言，亦即， FA 与正则文法与正
39、则文法 RG 等价。等价。FA FA 是正则语言的识别器是正则语言的识别器定理定理 3-33-3： FA FA 接受的语言是正则语言。接受的语言是正则语言。定理定理 3-43-4： 正则语言都可以被正则语言都可以被 FA FA 接受。接受。FA FA 是正则语言的识别器是正则语言的识别器求证方法：求证方法：1、FA 与右线性文法等价。与右线性文法等价。2、FA 与左线性文法等价。与左线性文法等价。FA 与与 G 等价的等价的证明思路：证明思路： 1、 给定给定 FA，构造相应的正则文法，构造相应的正则文法 G，证明二者处理的语，证明二者处理的语言相同。言相同。2、 给定正则文法给定正则文法 G
40、，构造相应的，构造相应的 FA ，证明二者处理的，证明二者处理的语言相同。语言相同。FA FA 是正则语言的识别器是正则语言的识别器 - - FA FA 与右线性文法与右线性文法DFA M = ( Q, , , q0, F ): q0 a1a2an-1an |- a1q1a2 an-1an |- a1a2q2 an-1an. |- a1a2 an-1 qn-1 an |- a1a2 an-1 an q n右线性文法右线性文法 G = ( V, T, P, A0 )： A0 a1A1 a1a2A2 . a1a2an-1An-1 a1a2an-1an注：注：1、变量、变量 A0 对应状态对应状态
41、q0；变量；变量 A1 对应状态对应状态 q1；依次类推。；依次类推。二者对应关系：二者对应关系：2、 FA 移至状态移至状态 qn F 结束，结束，G 中中 q a 推出终极符号串，结束推出终极符号串，结束FA FA 是正则语言的识别器是正则语言的识别器 - - FA FA 与右线性文法与右线性文法证明步骤证明步骤 1： 设设 DFA M = （ Q, , , q0, F ）构造构造 M 相应的右线性文法相应的右线性文法 G = ( Q, , P, q0 )，其中，其中 P = q ap | ( q, a ) = p q a | ( q, a ) = p F 使得使得 L( G ) = L(
42、 M ) - 。定理定理 3-33-3：FA FA 接受的语言是正则语言。接受的语言是正则语言。FA FA 是正则语言的识别器是正则语言的识别器 - - FA FA 与右线性文法与右线性文法证明步骤证明步骤 2： L（G）= L（M）- 对于任意对于任意 x = a1a2 an-1an + ，根据文法推导定义有，根据文法推导定义有: q0 a1a2 an-1an q0 a1q1, q1 a2q2，, qn-1 an P 由文法由文法 G 的构造定义的构造定义 ( q0, a1 ) = q1, (q1, a2 ) = q2, , ( qn-1, an ) = qn, 且且 qn F ( ( (
43、q0, a1 ), a2 ), an ) qn F DFA 接受字符串定义接受字符串定义 (q0, a1a2 an-1an ) = qn F 所以，所以， x = a1a2 an-1an L ( G ) x = a1a2 an-1an L ( M ) +FA FA 是正则语言的识别器是正则语言的识别器 - - FA FA 与右线性文法与右线性文法证明步骤证明步骤 3： 如果如果 q0 F，则，则 L（M），），L( G ) = L（M）- = L（M）已证）已证如果如果 q0 F，则，则 L（M），由以下已证定理可证：存在正则文法），由以下已证定理可证：存在正则文法 G，使得，使得 L（G）=
44、 L（G） = L（M）。）。第二章定理第二章定理 2- 6，2- 7 （P81 ） ：以下命题成立。：以下命题成立。 如果如果 L 是是 CSL，则，则 L （ L - ）仍然是）仍然是 CSL。 如果如果 L 是是 CFL，则，则 L （ L - ）仍然是）仍然是 CFL。 如果如果 L 是是 RL，则，则 L （ L - ）仍然是）仍然是 RL。FA FA 是正则语言的识别器是正则语言的识别器 - - FA FA 与右线性文法与右线性文法例例1：给定：给定 DFA M 如图，构造求解与其等价的正则文法如图，构造求解与其等价的正则文法 G。（1）（2）解：解：证明步骤证明步骤 1：设有右线
45、性正则文法设有右线性正则文法 G = （ V, T, P, S ），），构造与构造与 G 相应的相应的 DFA M，使得，使得 L（M）= L（G）。）。取取 M = ( V Z , T, , S, Z )，其中，其中, 对于对于 (A, a) VT，有有 B | A aB P Z 如果有如果有 A a P，添加，添加Z ( A, a ) = B | A aB P 如果如果 A a PFA FA 是正则语言的识别器是正则语言的识别器 - - FA FA 与右线性文法与右线性文法定理定理 3-43-4：正则语言都可以被正则语言都可以被 DFA DFA 接受。接受。FA FA 是正则语言的识别器是
46、正则语言的识别器 - - FA FA 与右线性文法与右线性文法 证明步骤证明步骤 2： L（G）= L（M） 对于字符串对于字符串 a1a2 an-1 an T+ ，根据文法推导产生语言定义：，根据文法推导产生语言定义： a1a2 an-1an L（G） S a1a2 an-1an S a1A1 a1a2A2 a1a2 an-1an 有产生式集合有产生式集合 S a1A1, A1 a2A2, , An-1 an P由由 DFA 构造定义构造定义 ( S, a1)= A1,( A1, a2)= A2, ., ( An-1, an)= Z Z ( ( ( S, a1 ), a2 ), an ) Z
47、 ( S, a1 a2 an-1 an ) a1a2 an-1an L（M ）+FA FA 是正则语言的识别器是正则语言的识别器 - - FA FA 与与右右线性文法线性文法 例：构造与给定右正则文法等价的例：构造与给定右正则文法等价的 FA。FA M = ( A, B, C, E, Z , 0, 1 , , E, Z )起始态起始态 E终止态终止态 Z解解：FA FA 是正则语言的识别器是正则语言的识别器 - - FA FA 与右线性文法与右线性文法由定理由定理 3-3，定理，定理 3-4 获推论获推论 3-1：FA 与正则文法等价。与正则文法等价。关系对应小结：关系对应小结：1、右线性文法
48、、右线性文法 G 产生式中的语法变量与产生式中的语法变量与 FA 状态转移函数中的状态对状态转移函数中的状态对应，即，应，即，A q；2、文法、文法 G 的起始符的起始符 S 与与 FA 的起始的起始状态状态 q0 对应，即，对应，即，S q0；3、右线性文法、右线性文法 G 的产生式与的产生式与 FA 的状态转移函数对应，即，的状态转移函数对应，即， A a B B =( A, a )；4、G 获终极字符串、获终极字符串、FA 的终止状态的终止状态 Z F 决定推导过程结束。决定推导过程结束。FA FA 是正则语言的识别器是正则语言的识别器 - - FA FA 与左线性文法与左线性文法DFA
49、 M =（ Q, , , q0, F ）：）：1、从开始符、从开始符 q0 开始，按照句子开始，按照句子 a1 a2 an 中字符出现顺序依次处理中字符出现顺序依次处理字符；每处理一个字符转入一个状态，最后停止在某个终止状态字符；每处理一个字符转入一个状态，最后停止在某个终止状态 ;2、每次处理且仅处理一个字符，第、每次处理且仅处理一个字符，第 i 步处理输入字符步处理输入字符 ai；3、根据状态转移函数、根据状态转移函数 ( q，a ) = p，在状态，在状态 q 下处理字符下处理字符 a；然后，；然后，从状态从状态 p 开始继续处理后续字符；开始继续处理后续字符；4、当、当( q，a )
50、= p F 且且 a 是输入串最后一个字符时是输入串最后一个字符时 ，M 处理完输处理完输入字符串。入字符串。DFA 与左线性文法之间的对应关系：与左线性文法之间的对应关系： G = （V，T，P，S），）， A ； A B:1、起始符、起始符 S 开始，推导每个句型右部左侧有且仅有一个语法变量；它们依开始，推导每个句型右部左侧有且仅有一个语法变量；它们依次归约出句子：次归约出句子：S Anan An-1an-1an, , Aa1 an-1an aa1 an-1an ；2、产生式、产生式 A Ba 表明：要使表明：要使 Ba 成立，可归约为求解成立，可归约为求解 A 有解。有解。 3、产生式、
