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

2023-03-27 20:35:11 浏览数 (1)

文章目录

  • I . 上下文无关语言 ( CFL ) 的 泵引理 ( Pumping Lemma )
    • II . 上下文无关语言 ( CFL ) 的 泵引理 ( Pumping Lemma ) 示例
    • III . 自动机扩展
I . 上下文无关语言 ( CFL ) 的 泵引理 ( Pumping Lemma )

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

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

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

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

假设

A

是 上下文无关的语言 ( CFL ) , 一定会存在一个 泵长度 ( Pumping Length )

p

, 使得

A

语言中的字符串长度都大于等于

p

,

A

语言中的每个字符串都可以被分为

S = uvxyz

五个部分 , 满足下面

3

个条件 :

  • ①
i geq 0

,

uv^i xy ^iz in A

; 其中

v^i

表示

i

个

v

串联在一起 , 如

v^3

就是

vvv

;

  • ②
|vy| geq 0

;

  • ③
|vxy| leq p

;

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

如果证明 某 语言不是 上下文无关语言 ( CFL ) , 先假设该语言是 CFL , 假如不符合上述

3

条件 , 说明假设不成立 , 该语言不是 CFL ;

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

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

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

C = { ww | w in {0,1}^* }

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

1 . 假设 : 假设

C

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

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

p

;

3 .

S

是 语言

C

的字符串 :

S = 0^p 1^p 0^p 1^p

;

4 . 泵引理 :

  • ①
i geq 0

,

uv^i xy ^iz in A

; 其中

v^i

表示

i

个

v

串联在一起 , 如

v^3

就是

vvv

;

  • ②
|vy| geq 0

;

  • ③
|vxy| leq p

;

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

5

部分 :

S = 0^p 1^p 0^p 1^p = uvxyz

其中

|vxy| leq 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

个栈的效果都是相同的 , 还是图灵机 ;

正则表达式 模型 优化 语法 字符串

0 人点赞