问题标签 [pumping-lemma]

如果L是正则语言，则存在一个常数n（取决于L），使得对于w语言中的每个字符串L，使得 的长度w大于或等于n，我们可以w分成三个字符串，w = xyz。

为什么要选择w大于或等于n？什么是泵送长度？

任何人都可以帮助弄清楚 L = { a ^m b ⁿ , m ≥ n + 2, m ≤ 3 } 是规则的还是不使用泵引理，这似乎有点难以证明。

我曾尝试使用抽引引理，它表明它是常规语言，但我真的很困惑这是对还是错。

对于 n>=0，给定的语法 (a^na^na^n) 上下文是否自由？我尝试使用抽引引理，结果是，不，它不是上下文无关的。

抽引引理定义（来自 wiki）

令 L 为常规语言。那么存在一个整数 p ≥ 1 仅取决于 L 使得 L 中的每个长度至少为 p 的字符串 w（p 称为“泵送长度”[4]）可以写成 w = xyz（即 w 可以是分为三个子串），满足以下条件：

|是| ≥1；|xy| ≤ p 对于所有 i ≥ 0，xyiz ∈ L

假设我要测试正则表达式 011 因为它是正则表达式m，所以存在至少长度为 p 的字符串 w 满足 w=xyz

这个自动机的数量是 3，p 应该 >= 3 但只有接受这个自动机的字符串是 011 所以我选择 011 因为 w 我可以分解 3 部分 011 = xyz 但我怎么能打破？我不能满足|y| ≥1；|xy| ≤ p 对于所有 i ≥ 0，xyiz ∈ L

由于它只接受 011 我该如何抽水？我哪里错了

{a^n | n >= 0}在 CS 课程中，我有以下示例：{a^p | p = prime number}

这些语言是正规的还是不正规的？有没有人可以提出引理矛盾？

斐波那契字符串定义如下： S1=a, S2=b 和 Sk=S k-1S k-2 for k>2 。例如 S3=ba ， S4=bab 等。令 L 为斐波那契字符串生成的语言。语言'L'是规则的吗？如果不是，请通过 Pumping Lemma 反驳。

如何计算常规语言的最小抽水长度。例如，如果我有 0001*，那么最小泵送长度应该是 4，即 000 不能被泵送。为什么会这样？

我想证明这种语言不是常规的 L={Am+n Bm C2n} 所以这就是我所做的：

设 m 为 L 的临界长度，长度 |W|>/m

我选择了 W=A3m Bm C2m

然后从抽水引理我得到： W=A3m Bm C2m 长度为 |YZ|<\m, |Y|>/1

因此： y=Bk, 1\

从抽水引理：YZiX∈L i=0,1,2,3...

因此： YZ0X=ZX∈L

因此： A3m Bk-m C2m ∉ L L={Am+n Bm C2n} 我们在这里有一个矛盾，因此语言不规则。这是正确的吗 ？或者你能告诉我正确的解决方案吗：D

是否有任何技巧可以通过仅查看语言来猜测语言是否是常规语言？

为了选择证明方法，首先我必须有一些假设。您是否知道在解决长问题时减少时间消耗所需的任何提示/模式？

例如，为了不花时间在引理上，当语言是规则的并且我不想构造 DFA/语法时。

例如：

只看上面的例子，如何判断哪个是常规的？

好的，我知道这不是一个编程问题，而是一个计算问题，所以它是相关的。

基本上，我如何使用抽水引理来证明这种语言不是正则的？

{w 在 {0,1}* | 如果 w 的长度为奇数，则中间符号为 0}

请尽可能简单地回答这个问题，虽然我知道计算模型，但我对它比较陌生。

非常感谢您！