1、1计算理论2主要内容2.1 上下文无关文法概述2.1.1 上下文无关文法的形式化定义2.1.2 上下文无关文法举例2.1.3 设计上下文无关文法2.1.4 歧义性2.1.5 乔姆斯基范式2.2 下推自动机2.2.1 下推自动机的形式化定义2.2.2 下推自动机举例2.2.1 与上下文无关文法的等价性2.3 非上下文无关语言3上下文无关文法 (CFG) 概述A 0A1A BB #替换规则变量 (Variables) A, B终止符 (Terminals) 0,1,#起始变元 (Start Variable) A箭头的左侧只有一个变量替换规则又称为产生式描述语言的方法：有穷自动机正则表达式4如何利
2、用 CFG 产生字符串A 0A1A BA #获取一个字符串的替换过程叫派生。例如字符串 000#111 的过程如下：A 0A1 00A11 000A111 000B111 000#111(1) 写下起始变元第一条规则左边的变元。(2) 取一个已写下的变元，并找到以该变元开始的规则，把这个变元替换成规则右边的字符串。(3) 重复步骤2，直到写下的字符串没有变元。5如何利用 CFG 产生字符串A 0A1A BA #可以用语法生成树形象地表示派生过程。AAAB#000 111A6文法的语言A 0A1A BA # 文法 G1 可以产生的字符串包括：#, 0#1, 00#11, 000#111, 用文法
3、 生成的所有字符串的集合称为文法的语言。 L(G1) 表示文法 G1 产生的语言。L(G1) = 0n#1n | n 0 用上下文无关文法产生的语言叫上下文无关语言。 文法 G1 的简写：A 0A1 | BB #7上下文无关文法的形式化定义定义2.1上下文无关文法是一个 4 元组 ( V, , R, S )，且(1) V 是一个有穷集合，称为变元集。 (2) 是一个与 V 不相交的有穷集合，称为终结符集。(3) R 是一个有穷规则集，每条规则由一个变元和一个由变元及终结符组成的字符串构成。(4) SV 是起始变元。8CFG的术语假设 u 与 v 由变元及终结符构成的字符串，Aw 是文法的一条规
4、则，称 uAv 生成 uwv，记作 uAv uwv 。如果 u = v ，或者 u1, u2, , uk, k 0 u u1 u2 uk v，则称 u 派生 v，记作 u * v。文法 G = (V,T,R,S)的语言为 L(G) = wT*| S w 9上下文无关文法举例例2.1 文法 G = ( S, a,b, R, S )， 规则集 R 为：S aSb | SS | 。该文法生成 abab，aaabbb，aababb， 如果 a 作 (， b 作 )，L(G)是所有正 的括 字符串构成的语言。10设计上下文无关文法设计如下语言的上下文无关文法0n1n | n 0 1 n0n | n 0 0n1n | n 01n0n | n 0设计 化繁为简，利用正则，考察子串，利用递归。
