常规语言的抽水引理是什么？

  • Z时代
  • 2024-01-10
  • 分类：综合

有两个 Pumping Lemmas (PL)，它们是为常规语言和上下文 - 自由语言定义的。

正则语言的抽引引理

  • 它提供了一种从给定字符串中抽取（生成）许多子字符串的方法。

  • 换句话说，我们说它提供了将给定的长输入字符串分成几个子字符串的方法。

  • Lt 给出condition(s)了证明一组字符串不规则的必要条件。

定理

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

|w|>=P

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

(1)lxyl < P

(2)lyl > 1

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

泵引理的应用

Pumping lemma 用于表明某些语言是不规则的。

它永远不应该被用来表明一种语言是规则的。

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

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

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

  • 步骤 1 - 我们必须假设 L 是正则的

  • 步骤 2 - 因此，泵引理应该对 L 成立。

  • 步骤 3 - 它必须有一个泵送长度（比如 P）。

  • 步骤 4 - 所有比 P 更长的字符串都可以抽 |w|>=p。

  • 步骤 5 - 现在在 L 中找到一个字符串 'w' 使得 |w|>=P

  • 步骤 6 - 将 w 分成 xyz。

  • 步骤 7 - 证明对于某些 i ，xy i z ∉ L。

  • 步骤 8 - 然后考虑 w 可以分为 xyz 的所有方式。

  • 步骤 9 - 表明这些都不能同时满足所有 3 个泵送条件。

  • 步骤 10 - w 不能被泵送 = CONTRADICTION。

以上是 常规语言的抽水引理是什么？ 的全部内容， 来源链接： utcz.com/z/356147.html

回到顶部