- 1、本文档共98页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第05章 正则语言的性质-28、29、30节课-2013-11-12
* * 5.4 关于正则语言的判定算法 定理 5-13 设L是字母表∑上的 RL ,对任意x∈∑*,存在判定x是不是L的句子的算法。 从一定的意义上讲,接受L的DFA M就是 判定x是否L的一个句子的“算法”。 * * 5.5 小结 本章讨论了RL的性质。包括: RL 的泵引理,RL 关于并、乘积、闭包、补、交、正则代换、同态、逆同态等运算的封闭性。Myhill-Nerode定理与FA的极小化。 ⑴ 泵引理。泵引理是用RL的必要条件来用来证明一个语言不是 RL 的。它不能用来证明一个语言是 RL,而且是采用反证法。 * * 5.5 小结 ⑵ RL 对有关运算的封闭性。RL 在并、乘、闭包、补、交、正则代换、同态映射运算下是有效封闭的。RL 的同态原像是 RL 。 ⑶ 设 L1、L2?∑*,如果L1是 RL ,则L1/L2也是 RL 。 * * 5.5 小结 ⑷ 如果L是RL,则根据RL确定的∑*的等价类可以构造出接受L的最小DFA。更方便的方法是通过确定给定DFA状态的可区分性构造出等价的最小DFA。 ⑸ 存在判定L(M)是非空、M1与 M2是否等价、L(M)是否无穷、x是不是RL L的句子的算法。 * * 5.3.1 Myhill-Nerode 定理 ⑵ RL 是右不变的。 设x RL y。由RL的定义,对?w,v∈∑*,xwv∈L ? ywv∈L,注意到v的任意性,知, xw RL yw。 所以,RL是右不变的等价关系。 * * 5.3.1 Myhill-Nerode 定理 定义5-9 指数(index) 设R是∑*上的等价关系,则称|∑*/R|是R关于∑*的指数。简称为R的指数。简称∑*的关于R的一个等价类,也就是∑*/R的任意一个元素,为R的一个等价类 * * 5.3.1 Myhill-Nerode 定理 例 5-9 图5-4 所给DFA M所确定的RM的指数为6。RM将∑*分成6个等价类: set(q0)={(00)n | n≥0}; set(q1)={0(00)n | n≥0}; set(q2)={(00)n1 | n,m≥0}; set(q3)={0(00)n 1|n≥0}; set(q4)={0n 10k|n≥0,k≥1}; set(q5)={x|x为至少含两个1的串}。 * * 5.3.1 Myhill-Nerode 定理 RM是RL(M)的“加细”(refinement) ?x,y∈∑*,如果x RM y,必有x RL(M) y成立。即对于任意DFA M=(Q,∑,δ,q0,F)。 |∑*/RL(M)|≤|∑*/RM|≤|Q| 按照RM中被分在同一等价类的串,在按照RL(M)分类时,一定会被分在同一个等价类。 RM对∑*的划分比RL(M)对∑*的划分更“细”。称RM是RL(M)的“加细”(refinement)。 * * 5.3.1 Myhill-Nerode 定理 ∑*/RM ={set(q0),set(q1),set(q2),set(q3),set(q4),set(q5)} ⑴ 取00∈set(q0),000∈set(q1)。 对于任意的x∈∑*,当x含且只含一个1时,00x∈L(M),000x∈L(M);当x不含1或者含多个1时,00x?L(M),000x?L(M)。这就是说,对于任意的x∈∑*,00x∈L(M) ? 000x∈L(M)。即按照RL(M),00与000被分在同一个等价类中。从而set(q0)和set(q1) 被包含在RL(M)的同一个等价类中。 * * 5.3.1 Myhill-Nerode 定理 ⑵ 取00∈set(q0),001∈set(q2)。 取特殊的字符串1∈∑*,001∈L(M),但0011?L(M)。所以,根据RL(M),set(q0)和set(q2)不能被“合并”到一个等价类中。 类似地,根据RL(M),set(q3)、set(q4)、set(q5)也都不能被“合并”到set(q0)的句子所在的等价类中。 * * 5.3.1 Myhill-Nerode 定理 ⑶ 取001∈set(q2),01∈set(q3)。 对于任意的x∈∑*,x要么不含1,要么含有1。当x不含1时,001x∈L(M),01x∈L(M); 当x含有1时,001x?L(M),01x?L(M)。这就是说,对于任意的x∈∑*,001x∈L(M) ? 01x∈L(M)。即按照RL(M),001与01属于RL(M)的同一个等价类中。从而set(q2)和set(q3) 被包含在RL(M)的同一个等价类中。 * * 5.3.1 Myhill-Nerode 定理 ⑷ 取1∈set(q2)
文档评论(0)