形式语言与自动机复习.pptVIP

College of Computer Science Technology, BUPT * * College of Computer Science Technology, BUPT 第二章 语言及文法 第三章 有限自动机和右线性文法 第四章 上下文无关文法与下推自动机 第五章 图灵机 复习课 * * College of Computer Science Technology, BUPT 第二章 语言及文法 语言的定义 字母表 字符串（句子） 连接运算 T*，T+ 语言，语言的积，语言的幂，L*，L+ 文法 文法的形式定义 推导，句型，句子 文法的分类 ０型，１型，２型和３型 * * College of Computer Science Technology, BUPT 第三章 有限自动机和右线性文法 有限自动机定义，识别的语言，格局 不确定的有限自动机NFA DFA与NFA等效 有 ?转换的NFA 有?转换的NFA和无?转换的NFA等效 正则集与正则式 右线性文法与正则集 正则表达式和有限自动机 右线性语言与有限自动机 右线性语言的性质　　　DFA的化简，泵浦引理 双向和有输出的有限自动机　２DFA，米兰机，摩尔机 * * College of Computer Science Technology, BUPT 第四章 上下文无关文法与下推自动机 推导树与二义性 上下文无关文法的变换 Chomsky范式和Greibach范式 下推自动机 上下文无关文法与下推自动机 上下文无关语言的性质 受限型上下文无关文法 * * College of Computer Science Technology, BUPT 第五章　图灵机 基本图灵机 图灵机的构造技术 * * College of Computer Science Technology, BUPT 练习题 证明L={??|??{a,b}*}不是3型语言。 设计摩尔机，接受０,1组成的串，且首符为１，中间只许出现１个０，若接受，输出y，否则输出n。 证明L={ambn|n=m2}不是2型语言。 L={??|??{a,b}*}，求产生L的Greibach范式文法G，及空栈接受L的NPDAM。 L={?|??{a,b}*且?含a,b的个数相同}，求产生L的Greibach范式文法G，及空栈接受L的NPDAM。 设计图灵机，将输入带上a,b组成的串取逆后放回原处，字符以外的单元为B。 * * College of Computer Science Technology, BUPT Exercise 给出T={a,b} 上能满足下列条件的语言的文法： 至少有3个a的所有符号串 a的个数不多于3的所有符号串 * * College of Computer Science Technology, BUPT Exercise 给出T={a} 上能满足下列条件的语言的文法： L={w | |w| mod 3 =0 } L={w | |w| mod 3 0 } L={w | |w| mod 3 |w| mod 2 } * * College of Computer Science Technology, BUPT Exercise 考虑以下两个语言： L1 = {anb2ncm | n, m ≥ 0} L2 = {anbmc2m | n, m ≥ 0} a) 通过分别给出上述语言的文法来证明这些语言都是上下文无关的。 b) L1∩L2是CFG吗？证明你的结论的正确性。 参考解答： a）定义文法 G1 的产生式集合为： S ? AB A ? aAbb?? B ? cB?? 定义文法 G2 的产生式集合为： S ? AB A ? aA?? B ? bBcc?? 可以证明 L1=L(G1)，L2=L(G2). b）L1∩L2 = { anb2nc4n | n ≥ 0}不是CFG. 可以用Pumping引理证明之. 对于任意的n，存在z=anb2nc4n 属于该语言. 令 z=w1w2w0w3w4，其中，?w2w0w3? ? n， w2w3??， 若取k=0，则 w1w2kw0w3kw4不属于该语言(分析略)，因此该语言不是2型语言. * 递归语言是这样的语言，它们至少被一个在所有输入上都能停止的图灵机所接受 一般而言，被图灵机计算的函数f（i1,i2…,ik）是部分递归函数，部分递归函数被一个在给定输入上可停可不停的图灵机计算。 * * College of Computer Science Technology, BUPT