文章目录
I . 上下文无关语言 ( CFL ) 的 泵引理 ( Pumping Lemma )
II . 上下文无关语言 ( CFL ) 的 泵引理 ( Pumping Lemma ) 示例
III . 自动机扩展
I . 上下文无关语言 ( CFL ) 的 泵引理 ( Pumping Lemma )
有些语言 在 上下文无关语法 与 下推自动机 计算能力之外 ;
通过 上下文无关语言 ( CFL ) 的 Pumping Lemma ( 泵引理 ) 可以证明上述命题 ;
( 证明的不是充要条件 , 只证明必要条件 )
上下文无关语言 ( CFL ) 的 泵引理 ( Pumping Lemma ) :
假设 A AA 是 上下文无关的语言 ( CFL ) , 一定会存在一个 泵长度 ( Pumping Length ) p pp , 使得 A AA 语言中的字符串长度都大于等于 p pp , A AA 语言中的每个字符串都可以被分为 S = u v x y z S = uvxyzS=uvxyz 五个部分 , 满足下面 3 33 个条件 :
① i ≥ 0 i \geq 0i≥0 , u v i x y i z ∈ A uv^i xy ^iz \in Auv
i
xy
i
z∈A ; 其中 v i v^iv
i
表示 i ii 个 v vv 串联在一起 , 如 v 3 v^3v
3
就是 v v v vvvvvv ;
② ∣ v y ∣ ≥ 0 |vy| \geq 0∣vy∣≥0 ;
③ ∣ v x y ∣ ≤ p |vxy| \leq p∣vxy∣≤p ;
这是一个必要条件 , 如果某语言是 上下文无关语言 , 那么符合上述要求 ; 反过来 , 如果不符合上述要求 , 什么都不能代表 , 该语言可能是 CFL , 也可能不是 CFL ;
如果证明 某 语言不是 上下文无关语言 ( CFL ) , 先假设该语言是 CFL , 假如不符合上述 3 33 条件 , 说明假设不成立 , 该语言不是 CFL ;
正则表达式 也有一个 泵引理 , 注意区分 ;
II . 上下文无关语言 ( CFL ) 的 泵引理 ( Pumping Lemma ) 示例
使用 上下文无关语言 ( CFL ) 的 泵引理 ( Pumping Lemma ) 证明
C = { w w ∣ w ∈ { 0 , 1 } ∗ } C = \{ ww | w \in \{0,1\}^* \}
C={ww∣w∈{0,1}
∗
}
不是 上下文无关语言 ( CFL ) ;
1 . 假设 : 假设 C CC 是 上下文无关语言 ( CFL ) ;
2 . 泵长度 : 根据 泵引理 , 存在一个 泵长度 p pp ;
3 . S SS 是 语言 C CC 的字符串 : S = 0 p 1 p 0 p 1 p S = 0^p 1^p 0^p 1^pS=0
p
1
p
0
p
1
p
;
4 . 泵引理 :
① i ≥ 0 i \geq 0i≥0 , u v i x y i z ∈ A uv^i xy ^iz \in Auv
i
xy
i
z∈A ; 其中 v i v^iv
i
表示 i ii 个 v vv 串联在一起 , 如 v 3 v^3v
3
就是 v v v vvvvvv ;
② ∣ v y ∣ ≥ 0 |vy| \geq 0∣vy∣≥0 ;
③ ∣ v x y ∣ ≤ p |vxy| \leq p∣vxy∣≤p ;
5 . 根据泵引理 , 将其分为 5 55 部分 :
S = 0 p 1 p 0 p 1 p = u v x y z S = 0^p 1^p 0^p 1^p = uvxyz
S=0
p
1
p
0
p
1
p
=uvxyz
其中 ∣ v x y ∣ ≤ p |vxy| \leq p∣vxy∣≤p ;
6 . v vv 和 y yy 相等的情况讨论 :
其中 v vv 和 y yy 不能同时是 0 00 或 1 11 , 如果 v y vyvy 同时是一个数 ( 0 00 或 1 11 ) , 如果重复 v vv 和 y yy 部分 , 该重复的数字会增多 , 如 0 00 增多 , 1 11 没有增多 , 导致字符串不符合语言的要求 ;
因此 v vv 和 y yy 必须是不同的 字符 , 一个是 0 00 一个是 1 11 ;
7 . v vv 和 y yy 取值不等 并处于 中间的 10 1010 之间的情况讨论 :
如果 v vv 和 y yy 处于中间的 1 11 和 0 00 之间 , 那么 v vv 和 y yy 同时增加后 , 第一个 0 00 与 第三个 0 00 个数不再相等 , 第二个 1 11 与 第四个 1 11 个数不再相等 , 不符合语言要求 ;
8 . v vv 和 y yy 取值不等 并处于 左侧的 01 0101 之间的情况讨论 :
如果 v vv 和 y yy 处于左侧的 0 00 和 1 11 之间 , 那么 v vv 和 y yy 同时增加后 , 第一个 0 00 与 第三个 0 00 个数不再相等 , 第二个 1 11 与 第四个 1 11 个数不再相等 , 不符合语言要求 ;
9 . v vv 和 y yy 取值不等 并处于 右侧的 01 0101 之间的情况讨论 :
如果 v vv 和 y yy 处于右侧的 0 00 和 1 11 之间 , 那么 v vv 和 y yy 同时增加后 , 第一个 0 00 与 第三个 0 00 个数不再相等 , 第二个 1 11 与 第四个 1 11 个数不再相等 , 不符合语言要求 ;
10 . 结论 :
因此该字符串 不满足 上下文无关语言 ( CFL ) 的泵引理 ;
假设不成立 , 因此该语言 C CC 不是上下文无关语言 ;
引申 : 下推自动机 之所以无法识别 C CC 这个语言 , 是因为下推自动机的 栈是后进先出的 , 先入栈的字符 , 后出来 , 这样就使得 前后相等 的字符串无法识别 , 镜面反射的字符串可以被识别 , 如果将栈替换成 先进先出的队列 , 那么就可以识别 语言 C CC 了 ;
III . 自动机扩展
1 . 确定性优先自动机 ( DFA ) 最小化 : 确定性有限自动机 ( DFA ) 有算法可以将其最小化 , 可以找到一个最小的确定性优先自动机 与 原来的 确定性有限自动机 ( CFG ) 等价 ;
( 等价的 确定性有限自动机 DFA 所识别的语言是相同的 )
2 . 下推自动机 ( PDA ) 无法最小化 , 也无法做等价判定 ;
给定一个下推自动机 ( PDA ) , 无法优化该下推自动机 ( PDA ) , 也无法得到一个最小的下推自动机 ;
两个 下推自动机 ( PDA ) 是否等价 也无法进行判定 ;
3 . 语言 与 计算模型 :
① 正则语言 : 对应的计算模型是 有限自动机 ( FA ) , 包括 确定性有限自动机 ( DFA ) , 非确定性有限自动机 ( NFA ) ;
② 上下文无关语言 : 对应的计算模型是 上下文无关语法 ( CFG ) , 下推自动机 ( PDA ) ;
4 . 自动机演化
① 下推自动机 ( PDA ) : 下推自动机 ( PDA ) 比 确定性有限自动机 ( DFA ) 多了一个栈结构 ;
② 图灵机 : 图灵机 比 下推自动机 多了一个栈 , 图灵机 有 2 22 个栈结构 ;
③ 自动机扩张 : 再加一个栈 , 3 33 个栈的效果与 2 22 个栈的效果基本相同 , 大于等于 2 22 个栈的效果都是相同的 , 还是图灵机 ;
