【计算理论】下推自动机 PDA ( 上下文无关语言 CFL 的 泵引理 | 泵引理反证示例 | 自动机扩展 )

I . 上下文无关语言 ( CFL ) 的 泵引理 ( Pumping Lemma )

有些语言 在 上下文无关语法 与 下推自动机 计算能力之外 ;

通过 上下文无关语言 ( CFL ) 的 Pumping Lemma ( 泵引理 ) 可以证明上述命题 ;

( 证明的不是充要条件 , 只证明必要条件 )

上下文无关语言 ( CFL ) 的 泵引理 ( Pumping Lemma ) :

假设 $A$ 是 上下文无关的语言 ( CFL ) , 一定会存在一个 泵长度 ( Pumping Length ) $p$ , 使得 $A$ 语言中的字符串长度都大于等于 $p$ , $A$ 语言中的每个字符串都可以被分为 $S=uvxyz$ 五个部分 , 满足下面 $3$ 个条件 :

• ① $i\ge 0$ , $u{v}^{i}x{y}^{i}z\in A$ ; 其中 $v^i$ 表示 $i$ 个 $v$ 串联在一起 , 如 $v^3$ 就是 $vvv$ ;
• ② $|vy|\ge 0$ ;
• ③ $|vxy|\le p$ ;

这是一个必要条件 , 如果某语言是 上下文无关语言 , 那么符合上述要求 ; 反过来 , 如果不符合上述要求 , 什么都不能代表 , 该语言可能是 CFL , 也可能不是 CFL ;

如果证明 某 语言不是 上下文无关语言 ( CFL ) , 先假设该语言是 CFL , 假如不符合上述 $3$ 条件 , 说明假设不成立 , 该语言不是 CFL ;

正则表达式 也有一个 泵引理 , 注意区分 ;

II . 上下文无关语言 ( CFL ) 的 泵引理 ( Pumping Lemma ) 示例

使用 上下文无关语言 ( CFL ) 的 泵引理 ( Pumping Lemma ) 证明

$$C=\{ww|w\in \{0,1{\}}^{\ast }\}$$

不是 上下文无关语言 ( CFL ) ;

1 . 假设 : 假设 $C$ 是 上下文无关语言 ( CFL ) ;

2 . 泵长度 : 根据 泵引理 , 存在一个 泵长度 $p$ ;

3 . $S$ 是 语言 $C$ 的字符串 : $S=0^p{1}^p{0}^p{1}^p$ ;

4 . 泵引理 :

• ① $i\ge 0$ , $u{v}^{i}x{y}^{i}z\in A$ ; 其中 $v^i$ 表示 $i$ 个 $v$ 串联在一起 , 如 $v^3$ 就是 $vvv$ ;
• ② $|vy|\ge 0$ ;
• ③ $|vxy|\le p$ ;

5 . 根据泵引理 , 将其分为 $5$ 部分 :

$$S=0^p{1}^p{0}^p{1}^p=uvxyz$$

其中 $|vxy|\le p$ ;

6 . $v$ 和 $y$ 相等的情况讨论 :

其中 $v$ 和 $y$ 不能同时是 $0$ 或 $1$ , 如果 $vy$ 同时是一个数 ( $0$ 或 $1$ ) , 如果重复 $v$ 和 $y$ 部分 , 该重复的数字会增多 , 如 $0$ 增多 , $1$ 没有增多 , 导致字符串不符合语言的要求 ;

因此 $v$ 和 $y$ 必须是不同的 字符 , 一个是 $0$ 一个是 $1$ ;

7 . $v$ 和 $y$ 取值不等 并处于 中间的 $10$ 之间的情况讨论 :

如果 $v$ 和 $y$ 处于中间的 $1$ 和 $0$ 之间 , 那么 $v$ 和 $y$ 同时增加后 , 第一个 $0$ 与 第三个 $0$ 个数不再相等 , 第二个 $1$ 与 第四个 $1$ 个数不再相等 , 不符合语言要求 ;

8 . $v$ 和 $y$ 取值不等 并处于 左侧的 $01$ 之间的情况讨论 :

如果 $v$ 和 $y$ 处于左侧的 $0$ 和 $1$ 之间 , 那么 $v$ 和 $y$ 同时增加后 , 第一个 $0$ 与 第三个 $0$ 个数不再相等 , 第二个 $1$ 与 第四个 $1$ 个数不再相等 , 不符合语言要求 ;

9 . $v$ 和 $y$ 取值不等 并处于 右侧的 $01$ 之间的情况讨论 :

如果 $v$ 和 $y$ 处于右侧的 $0$ 和 $1$ 之间 , 那么 $v$ 和 $y$ 同时增加后 , 第一个 $0$ 与 第三个 $0$ 个数不再相等 , 第二个 $1$ 与 第四个 $1$ 个数不再相等 , 不符合语言要求 ;

10 . 结论 :

因此该字符串 不满足 上下文无关语言 ( CFL ) 的泵引理 ;

假设不成立 , 因此该语言 $C$ 不是上下文无关语言 ;

引申 : 下推自动机 之所以无法识别 $C$ 这个语言 , 是因为下推自动机的 栈是后进先出的 , 先入栈的字符 , 后出来 , 这样就使得 前后相等 的字符串无法识别 , 镜面反射的字符串可以被识别 , 如果将栈替换成 先进先出的队列 , 那么就可以识别 语言 $C$ 了 ;

III . 自动机扩展

1 . 确定性优先自动机 ( DFA ) 最小化 : 确定性有限自动机 ( DFA ) 有算法可以将其最小化 , 可以找到一个最小的确定性优先自动机 与 原来的 确定性有限自动机 ( CFG ) 等价 ;

( 等价的 确定性有限自动机 DFA 所识别的语言是相同的 )

2 . 下推自动机 ( PDA ) 无法最小化 , 也无法做等价判定 ;

给定一个下推自动机 ( PDA ) , 无法优化该下推自动机 ( PDA ) , 也无法得到一个最小的下推自动机 ;

两个 下推自动机 ( PDA ) 是否等价 也无法进行判定 ;

3 . 语言 与 计算模型 :

① 正则语言 : 对应的计算模型是 有限自动机 ( FA ) , 包括 确定性有限自动机 ( DFA ) , 非确定性有限自动机 ( NFA ) ;

② 上下文无关语言 : 对应的计算模型是 上下文无关语法 ( CFG ) , 下推自动机 ( PDA ) ;

4 . 自动机演化

① 下推自动机 ( PDA ) : 下推自动机 ( PDA ) 比 确定性有限自动机 ( DFA ) 多了一个栈结构 ;

② 图灵机 : 图灵机 比 下推自动机 多了一个栈 , 图灵机 有 $2$ 个栈结构 ;

③ 自动机扩张 : 再加一个栈 , $3$ 个栈的效果与 $2$ 个栈的效果基本相同 , 大于等于 $2$ 个栈的效果都是相同的 , 还是图灵机 ;

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/106254758