单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级College ofputer Science Technology BUPT第三章 有限自动机与右线性文法本章主要内容确定有限自动机非确定有限自动机确定与非确定有限自动机的等价性右线性文法和有限自动机的等价性右线性文法的性质(泵浦定理)使用归纳法进行证明的方法1College ofputer Science
College ofputer Science Technology BUPTq0? - NFA 的形式定义q2 状态 q 的? - 闭包记为 ? - CLOSURE 或ECLOSE 定义为从 q 经所有的? 路径可以到达的状态(包括q自身)如: 51ε-NFA中δ与δ 函数的不同 1. ? -NFA<==>NFA具有?转移的NFA是不具?转移的NFA的一般情况 所以只要证明下面
College ofputer Science Technology BUPTCollege ofputer Science Technology BUPT归约与推导(3)vOE 推导过程举例 对于CFG Gexp = ({EO} { ( ) ? v d } P E ) P 为 (1)E ? EOE
1College ofputer Science & Technology, BUPT第四章上下文无关文法与下推自动机 推导树和文法的 二义性上下文无关文法的变换Chomsky范式Greibach范式 下推自动机上下文无关语言的性质2College ofputer Science & Technology, BUPT本章要点上下文无关文法(即2型文法): 产生式形如 A→α, A?
#
单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级College ofputer Science Technology BUPT§ 4.2 上下文无关文法的变换 CFG 的简化消无用符号消 ? 产生式消单产生式对生成式形式进行标准化1College ofputer Science Technology BUPT生成式的标准形式 Chomsky范式
#
#
引例 正则表达式的形式定义.1形式定义.2 例题 正则表达式与有穷自动机的等价性.1充分性证明.2必要性的证明(1)首先说明如何把DFA转换成GNFA(2)说明如何把GNFA转换成正则表达式例题2:正则表达式(0∪1)其值为:由0和1的所有字符串组成的语言也表示为{0 1}表示方法:记∑为字母表∑也可以表示该字母表中所有长度为1的字符串而∑为由该字母表中所有字符串组成的语言如:(0∑)∪(∑1)表
#
违法有害信息,请在下方选择原因提交举报