alLanguagesandAutomataTheory-第六章-课件.ppt

FormalLanguagesandAutomataTheory 6上下文无关文法与下推自动机 语言 aibi i 0 是不能被有穷自动机所接受的 要接受这个语言 机器需要记录某一a的有限次数 有限状态机的约束不允许自动机 记住 输入串中a的个数 因此我们需要定义一个新型自动机 它由一个下推栈加上一个有限自动机组成 称为下推自动机 PDA 6 1下推自动机 1 定义 下推自动机 pushdownautomation 是一个七元组 Q q0 z F 其中Q是一有穷状态集 为一有穷字母表 为一有一有穷下推集 q0为开始状态 z为下推字符 F Q是终止状态集 是从Q P 到Q P 的转移函数 一个PDA有两个字符集 输入字符串 它由输入字符串组成 有一个栈字符集P 它的元素存在栈中 A 表示以A为栈顶元素的栈 空栈被表示为 PDA的计算开始于状态q0 输入在输入带上且栈为空 PDA的当前状态 输入符号和栈顶符号决定自动机的转换 转换函数 列出所有给定状态 符号和栈顶元素的所有可能的转换 qi a A qj B qk C 表示当前状态为qi 输入符号为a 栈顶符号为A时的两种可能的转换 6 1下推自动机 2 qj B qi a A newstatecurrentstacktopnewstacktopcurrentinputsymbolcurrentstate表示i 状态由qi换为qiii 处理字符a 输入带向前移动iii 栈顶A退栈iv B进栈 6 1下推自动机 3 一个下推自动也可由状态转换图表示 弧上的符号表示输入符号和栈操作 转换函 qj B qi a A 表示如下 aA Bqiqj符号 表示B代替A 可以出现在输入字符和栈顶位置 分别三种转换函数 1 qi qi A 输入位置是 A A出栈qi 6 1下推自动机 4 2 qi A qi 输入位置是 A A压栈 不改变输入状态 qi 3 qj qi a a 等价于有限自动机 转换由状态和输入符号决定 qiqj一个PDA可表示为一个三元组 qi qi是机器状态 为未处理的输入串 为栈顶 qi qj v 表示 qj v 由 qi 经一步转换而得 6 1下推自动机 5 例1 构造一个PDA接受语言 aibi i 0 M Q q0 q1 a AbA bA a b A F q0 q1 q0 a q0 A q0 b A q1 q1 b A q1 q0 aabb q0 abb A q0 bb AA q0 b A q0 q0q1 6 1下推自动机 6 定义 设M Q q0 F 为一PDA 字符串 被PDA接受 如果 q0 qi qi F 终态的集合 例2 PDAM接受语言 c R a b M Q q0 q1 a b c A B F q1 q0 a q0 A b BbB q0 b q0 B a AaA q0 c q1 q0c q1 q1 a A q1 q1 b B q1 6 1下推自动机 7 例3 PDAM接受语言 ai i 0 aibi i 0 a AbA q0bA q1 q2 A 6 1下推自动机 8 例4 含有相同个数的0和1的所有的0 1串 思想 用栈记录0和1个数的差 当1比0多时 栈中全部为A 且A的个数等于1比0多的个数 当0比1多时 栈中全部为B 且B的个数等于0比1多的个数 M q p 0 1 A B Z q Z p 其中 q Z p 接受 读完字符串后栈中没有A或B 转到终止状态 q 1 Z q A 在前面0和1个数相等的时候又读到1 则在栈中压入1个A q 0 Z q B 在前面0和1个数相等的时候又读到0 则在栈中压入1个B q 1 A q AA 在前面1比0个数多的时候又读到1 则在栈中再压入1个A q 0 A q 在前面1比0个数多的时候又读到0 则从栈中弹出1个A q 1 B q 在前面0比1个数多的时候又读到1 则从栈中弹出1个B q 0 B q BB 在前面0比1个数多的时候又读到0 则在栈中压入1个B根据文法构造G S 1S0S 0S1S 构造语言的NPDA 6 2下推自动机与上下文无关文法 一个上下文无关语言都存在一个NPDA能够授受它 反之亦然 1 上下文无关语言相应的下推自动机对于每一个上下文无关文法语言都存在一个NPDA可以接受它 它的基本思想是构造一个NPDA能够以某种方式对于该语言中任何符号串产生一个最左推导 为了对命题稍做简化 我们可以假定上下文无关语言是由格里巴克范式生成的 定理 对于任何的上下文无关文法语言L 存在一个NPDAM使得L L M 已知文法S aSbb a 构造NPDA 首先修改文法转换为格里巴克范式 S aSA aA bBB b 2 下推自动机相应的上下文无关文法使用文法模拟PDA的转移 这也就是说使句型中的变量部分反映栈的内容 而已处理的输入作为句型的仅含终结符前缀 为了简单 我们将假定问题中的NPDA满足如下条件 1 它只有一个终态qf 且当且仅当栈空是才进入终态 2 所有转移函数的形式应该是 qi a A c1 c2 cn 其中C qj 或C qj BC 定理 对于任何一个NPDAM 如果L L M 则L是上下文无关语言 6 3上下文无关语言的性质 泵引理 1 定理 2型语言的泵作用引理 设L是上下文无关语言 存在常数p 如果 L 且 p 则 可以写为 uvwxy 其中i vx ii vwx piii uviwxiy L i 0 线性语言的泵作用引理是说 在正规集合中 每个足够长的字符串都包含一个短的字串 随便将这个子串在原处重复插入多少次 所得的新字串还是在原正规集中 2型语言的泵引理是说 有两个靠得很近的子串 它们可以重复任意多次 但二者重复的次数相同 所得的新串依然属于该2型语言 6 3上下文无关语言的性质 泵引理 2 证明L anbncn n 1 不是2型语言 证 假设L是2型语言 取常数p apbpcp 3p p将 写成 uvwxy其中 vx 1且 vwx p考虑vwx在 中所处的位置 如果v含有a x含有c apbpcp则有 vwx 最小为 abpc p 2 p 不满足泵作用引理的条件 如果v x都含有a b或c apbpcp可写成 aiap 2 i jajbpcpvwx将v x重复2次 将有 a2iap 2 i ja2jbpcp L a的个数大于b和c的个数 与2型语言的假设矛盾 6 3上下文无关语言的性质 泵引理 3 若v x分别包含a和b b和c 当取w aaap 2bbp 1cp时uvwxy将v x重复2次 将有 aa2ap 2b2bp 1cp Lvwx 其中a b个数将大于c的个数 与2型语言假设矛盾 综上 L不是2型语言 6 3上下文无关语言的性质 泵引理 4 证明 L a 的长度为质数 不是上下文无关文法 证明 设L是上下文无关文法 n是一个大于泵作用引理中p的素数 由泵作用引理知 an必须分解为uvwxy满足泵引理的条件令m u w y 任意串uviwxiy的长度是m i n m uvn 1 wxn 1 y m n 1 n m n n m 1 故uviwxiy的长度不是质数 所以L不是上下文无关文法 证明语言 anbjanbj i j 0 不是上下文无关语言 6 3上下文无关语言的性质 封闭性 1