本条目存在以下问题,请协助 改善本条目或在 讨论页针对议题发表看法。
此条目内容疑欠准确,有待查证。 (2021年2月22日) 请在讨论页讨论问题所在及加以改善,若此条目仍有争议及准确度欠佳,会被提出存废讨论。 |
|
在可计算性理论中的形式语言理论中,泵引理(Pumping lemma)声称给定类的任何语言可以被“抽吸”并仍属于这个类。一个语言可以被抽吸,如果在这个语言中任何足够长的字符串可以分解成片段,其中某些可以任意重复来生成语言中更长的字符串。这些引理的证明典型的需要计数论证比如鸽笼原理。
两个最重要例子是正则语言的泵引理和上下文无关语言的泵引理。鄂登引理是另一种更强的上下文无关语言的泵引理。
这些引理可以用来确定特定语言不在给定语言类中。但是它们不能被用来确定一个语言在给定类中,因为满足引理是类成员关系的必要条件,但不是充分条件。
泵引理是1961年由 Y. Bar-Hillel、M. Perles 和 E. Shamir首次发表的[1]。
正则语言的泵引理
定义
假设 是正则语言,则存在整数 ,对任意字符串 且 (n为泵长度,可理解为正则语言等效的极小化DFA的状态个数),可以将 写成 的形式,使得以下说法成立:
- ,
- ,
- 。
正确性的证明
- 因为L是正则语言,所以存在一个与之等价的确定有限状态自动机,
- 假设n是这个确定有限状态自动机中状态的数量,
- 假设 和
- 在这个自动机读入w的前n个字符后一定有一个状态达到过两次,
- 也就是说对于其中一种w的分解方式w=xyz有
- 因此对于所有的 都有
应用
通过泵引理可以用反证法证明L不是正则语言。证明的时候需要注意以下几点:
- 假设要证明的语言为正则语言
- 是未知的
- 可以在满足 和 的条件下自由选择
- 也是未知的
- 找到一个 ,使得 ,也就是说和泵引理的第三条矛盾
一个证明L不是正则语言的例子
- 证明 不是正则语言
- 假设 是正则语言,令n为泵引理常数
- 选择 ,则
- 于是存在 使得 满足条件 , , 。
- 因为 且, 所以 中不包含 但最少有一个
- 当 的时候, , 中 的数量比 多,所以
- 与泵引理的第三条矛盾,因此 不是正则语言
普遍化的泵引理[2]
并不是所有满足泵引理的语言都是正则语言。 就是这样的一个例子,它虽然满足泵引理,但并不是正则语言。Jeffrey Jaffe发展出了一个普遍化的泵引理,使它可以证明一个语言是正则语言。它的描述如下:
- 一个语言 是正则语言,当且仅当存在一个自然数 ,使得任意字符串 可以通过至少一种方式被写成 的形式时,以下说法成立:
- ,
- ,
- , 。
一个可行的用于判断一个语言是否为正则语言的方法,可以参见迈希尔-尼罗德定理。一般来说证明一个语言是正则的,可以通过对该语言构造一个有限状态机或正则表达式来实现。
上下文无关语言的泵引理
定义
若 L 是上下文无关语言,则存在一常数 n > 0 使得语言 L 中每个字串 w 的长度 |w| ≧ n,而当 w = uvxyz 时:
- |vxy| ≦ n,
- |vy| ≧ 1,且
- 对所有的 k ≧ 0,字串 uvkxykz 属于 L 。
应用
透过泵引理以反证法证明 L 不是上下文无关语言。
- 或 或 ,换句话说,L 就是包含 所有字串且 a、b、c 三者数目相同的语言。
- 令 n 为泵引理常数, 属于 L,w = uvxyz,而 |vxy| ≤ n,|vy| ≥ 1,则 vxy 不可能同时包含 a 与 c。
- 当 vxy 不包含 a 时,vy 只可能包含 b 或 c,则 uxz 包含 n 个 a 及不到 n 个的 b 或 c,使得 uxz 不属于 L。
- 当 vxy 不包含 c 时,uxz 会包含 n 个 c 及不到 n 个的 a 或 b,使得 uxz 不属于 L。
- 因此,无论是上述何种状况,L 都不会是上下文无关语言。
-
- 令 n 为泵引理常数, ,w = uvxyz,而 |vxy| ≤ n,|vy| ≥ 1
- 若 vxy 只包含 a,则 uxz 会包含不到 n 个 a 及 个 b,不属于 L;
- 若 vxy 只包含 b,则 uxz 会包含 n 个 a 及不到 个 b,不属于 L;
- 若 vxy 里有 a 也有 b,
- 若 v 或 y 包含 a 与 b, 不在 里;
- 若 v 只包含 l 个 a,且 y 只包含 m 个 b, 会包含 n + lk 个 a 与 个 b,由于两者都是线性成长,不可能永远满足 的条件,不属于 L。
- 因此,无论是上述何种状况,L 都不会是上下文无关语言。
-
- 令 n 为泵引理常数, 属于 L,w = uvxyz,而 |vxy| ≤ n,则 vxy 必然为 或 形式(此处有 )。即 vxy无法同时包含前后两组0,也无法同时包含前后两组1。将uvxyz转变成uxz必然导致前后两组0或两组1的数目产生差异。使得uxz不再满足ww形式。亦即uxz不属于L。
- 因此,L 都不会是上下文无关语言。
-
-
-
引用