正则语言的泵引理是什么？

有两个泵引理 (PL)，分别定义用于正则语言和上下文无关语言。

正则语言的泵引理

  • 它提供了一种从给定字符串中“泵出”（生成）许多子串的方法。
  • 换句话说，它提供了一种将给定的长输入字符串分解成几个子串的方法。
  • 它给出了证明一组字符串不是正则的必要条件。

定理

对于任何正则语言 L，存在一个整数 P，使得对于 L 中的所有 w

|w|>=P

我们可以将 w 分解成三个字符串，w=xyz，使得。

(1)|xy| < P

(2)|y| > 1

(3)对于所有 k>= 0：字符串 xykz 也在 L 中

泵引理的应用

泵引理用于证明某些语言不是正则的。

它不应用于证明语言是正则的。

  • 如果 L 是正则的，则它满足泵引理。
  • 如果 L 不满足泵引理，则它不是正则的。

**使用 PL 证明语言不是正则的步骤**如下：

  • 步骤 1 - 我们必须假设 L 是正则的
  • 步骤 2 - 因此，泵引理应该适用于 L。
  • 步骤 3 - 它必须有一个泵长度（例如 P）。
  • 步骤 4 - 所有长度大于 P 的字符串都可以泵出 |w|>=p。
  • 步骤 5 - 现在在 L 中找到一个字符串 'w'，使得 |w|>=P
  • 步骤 6 - 将 w 分解成 xyz。
  • 步骤 7 - 证明对于某些 i，xyiz ∉ L。
  • 步骤 8 - 然后考虑 w 可以分解成 xyz 的所有方式。
  • 步骤 9 - 证明这些方式中没有一个可以同时满足所有 3 个泵条件。
  • 步骤 10 - w 不能被泵出 = 矛盾。

更新于：2021年6月11日

54K+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告