;
( 证明的不是充要条件 , 只证明必要条件 )
上下文无关语言 ( CFL ) 的 泵引理 ( Pumping Lemma ) :
假设
A
是 上下文无关的语言 ( CFL ) , 一定会存在一个..., 如果某语言是 上下文无关语言 , 那么符合上述要求 ; 反过来 , 如果不符合上述要求 , 什么都不能代表 , 该语言可能是 CFL , 也可能不是 CFL ;
如果证明 某 语言不是 上下文无关语言...( CFL ) , 先假设该语言是 CFL , 假如不符合上述
3
条件 , 说明假设不成立 , 该语言不是 CFL ;
正则表达式 也有一个 泵引理 , 注意区分 ;
II ....下推自动机 ( PDA ) 无法最小化 , 也无法做等价判定 ;
给定一个下推自动机 ( PDA ) , 无法优化该下推自动机 ( PDA ) , 也无法得到一个最小的下推自动机 ;
两个 下推自动机...( PDA ) 是否等价 也无法进行判定 ;
3 .