问题标签 [pumping-lemma]

我试图L={y#x|(y is a substring of x) ∧x,y∈{a,b}^* }使用抽水引理证明这不是上下文无关的，但我似乎无法做到这一点。如果

然后要么vxy两者兼有a，b要么只有，b要么只有a。

我怎样才能抽它来显示呢？

所以这不是关于抽水引理及其工作原理，而是关于先决条件。

在网络上你可以读到的任何地方，常规语言都必须通过抽引引理，但是没有人谈论有限语言，它实际上是常规语言的一部分。

所以我们可能都同意，以下语言是一种有限语言，也是一种常规语言，但它绝对没有通过抽水引理：

L = {'abc', 'defghi'}

请告诉我是否根本没有人写它，或者我们为什么错了——甚至没有。

我正在学习问题中词条之间的区别。我能找到的每个参考都使用了这个例子：

以显示两者之间的区别。我可以找到一个使用常规引理来“反驳”它的例子。

选择 w = uvxyz, st |vy| > 0, |vxy| <= 页。假设 w 包含相等数量的 b、c、d。

我选择了：

抽 y 只会增加 a 的数量，如果 |b|=|c|=|d| 起初，它现在仍然会。

（如果 w 没有 a 的类似论点。然后随便抽你想要的。）

我的问题是，奥格登引理如何改变这种策略？“标记”有什么作用？

谢谢！

令 B 为语言 {0 ⁿ 1 ⁿ | n >= 0} 即 0 和 1 必须具有相同的长度

令 B 中的 s 为字符串 0 ^p 1 ^p

假设 B 是正则的，所以 s 必须能被 s = xyz 整除，其中 xy ⁱ z i>=0 仍在 B 中（泵引理的三个条件的条件 1）。

考虑 xy ⁱ z 的情况，其中 i = 2 所以 xyyz：泵 y 全为 0
xyyz 有更多的 0 和 1，因此它不能在 B 中。因此，B 不是规则的。

我很难理解如果 y 在 xyyz 中全为 0，那么 # of 0s > # of 1s

为什么不能|xyy| = |z| 那么它将具有相同的 0 和 1 数？

我需要一些帮助来解决抽水引理问题。

这是我到目前为止得到的：

我让 y = abbc^n，n 是来自抽水引理的长度。y 在 L 中是因为 a:s 的数量小于 b:s 的数量，并且 b:s 的数量小于 c:s 的数量。

我让 u = a，v = bb 和 w = c^n。|紫外线| < y，如抽水引理中所述。如果我“抽” (bb)^2 那么我得到

这是正确的吗 ？我在“正确的道路”上吗？

谢谢

我有一个关于上下文无关语言的特定泵引理问题的问题。

假设我们有以下语言：

这是我试图证明该语言不是上下文无关的尝试：

假设 L 与上下文无关。从引理中取常数 n>0。

比根据引理，Z 可以写成 Z = uvwxy，其中下列性质成立：

我们为 vwx 提供了 6 种不同的可能性

到目前为止这是对的吗？我不确定的事情是，我的不同 vwx 案例是否正确。

提前致谢

使用pumping lemma，我们可以很容易地证明该语言L1 = {WcW^R|W ∈ {a,b}*}是正则语言。（字母表是{a,b,c}；W^R 代表逆向字符串W）

但是，如果我们用 替换字符c，"x"(x ∈ {a,b}+)比如说L2 = {WxW^R| x, W ∈ {a,b}^+}，，那么 L2是一种常规语言。

你能给我一些想法吗？

众所周知，使用抽引引理，我们可以很容易地证明语言L = {WW|W ∈ {a,b}*}不是正则语言。

然而，语言，L1 = {W1W2| |W1| = |W2|} 是一种常规语言。因为我们可以像下面这样得到 DFA，

我的问题是，L = {WW|W ∈ {a,b}*}也有偶数长度的字符串（|w|=|w|，绝对），L 仍然可以有一些像上面那样的 dfa。怎么不是普通语言？

谢谢。

在检查给定语言是否使用抽引引理时，我有点困惑。

假设我们必须检查是否：

L. 是否接受偶数个0正则的语言？

我们知道它是有规律的，因为我们可以为 L 构造一个 DFA。但我想用泵引理来证明这一点。

现在假设，我接受一个 String w= "0000"：

现在将字符串划分为x = 0、y = 0和z = 00。现在在为 应用抽引理时i = 2，我将得到字符串"00000"，它在我的语言中不存在，因此通过抽引引理证明该语言不规则。但它被 DFA 接受了吗？

任何帮助将不胜感激
谢谢

我试图通过 Pumping Lemma 证明以下语言不规则。但我不确定我是否做得正确。

{L = a ^{2 n} | n>= 0 }

到目前为止，我所做的如下：

s = a ^{2 p}

x = 一个^2我

y = a ^{2 j}

z = a ^{2 p-ij}

因此 xy ² z = a ^{2 p+j}

这意味着 a ^{2 p+j} > a ^{2 p} ，使语言不规则

我做得对吗？还是我有什么问题？