问题标签 [pumping-lemma]

问问题

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

123 问题

0 投票

1 回答

497 浏览

computation - 抽引引理条件 3 概念

我正在关注我教科书中关于抽水引理的一个例子：

我无法理解条件 3 如何得出“y 必须仅由 0 组成，因此 xyyz 不在 C 中”的结论

computation pumping-lemma

0 投票

1 回答

2487 浏览

pumping-lemma - 这种语言是正规的吗？{a^ib^j| i=j mod 19}

我知道这{a^i b^j | i = j }不正常，我可以用抽引理证明；同样，我也可以使用抽引引理来证明这个不规则。但我想我看到了一些类似的问题，说这种语言实际上是有规律的。而且因为我对我在抽取引理方面的知识没有信心，所以我问了这个不好的问题。对不起。

这就是我证明它的方式：让 w be a^p b^(19k+p)，显然这是在语言中。然后，如果我抽一个，做它a^(p+1) b^(19k+p)。它失败。因此，它不是常规的。

我的证明对吗？

pumping-lemma

0 投票

2 回答

2023 浏览

regular-language - 有人可以使用抽水引理帮助我证明这个证明吗？

我刚刚开始阅读有关抽水引理的内容，并且知道如何进行一些证明，主要是通过矛盾。只有这个特殊的问题，我似乎没有找到答案。我不知道如何开始。我可以假设必须有一个泵送长度P，并且对于 L 的所有w元素，LENGTH(w) >= P. 当然，我们可以用xyz抽水引理的三个正常条件来写 w。

我必须证明以下语言是非常规的：

有人可以帮助我吗，我真的很想掌握证明这类问题的过程吗？

编辑：
对不起，忘了说字母表是字符串{0,1,+,=}的#二进制值。喜欢#(00101) = 5和#(110) = 6。

regular-language automata proof pumping-lemma

0 投票

0 回答

181 浏览

pumping-lemma - 为 CFL 泵送引理

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

我知道我需要使用抽水引理。所以我必须使用 w = uvxyz where |vy| > 0 和 |xyz| > p（泵送长度）。我知道我需要表明，当为每种情况抽取一个字符串时，它是在语言之外的。

我知道 v^i 或 y^i 包含某些内容而另一个为空但我不知道为我的字符串选择什么的情况。

pumping-lemma

0 投票

1 回答

679 浏览

pumping-lemma - anb2n+1 的抽引引理

我知道如何解决 a ⁿ b ⁿ的泵引理：n>=0 但我不明白如何解决这个例子：a ⁿ b ²ⁿ⁺¹ :n>=0

我试图解决它，但我不确定我是否正确解决了它？有人可以在这里帮助我吗？

我可以展示我是如何解决它的。但说真的，我不确定它是否正确。如果我错了，请给我正确的。

问题：证明 a ⁿ b ²ⁿ⁺¹ :n>=0 不是正则的。

这是我的答案。

假设 L 是正则的。那么抽引理必须成立。令 m 为 Pumping 引理中的整数。

令 w=a ^m b ^2m+1也在 L. 和 |w|>=m

通过抽取引理 w=xyz where |xy|<=m and |y|>=1

根据抽水引理 w _i =xy ⁱ z 也在 L for i=0,1,2,...

令 i=2 然后 w ₂ =xyyz。

设 y= ^ak其中 1<=k<=m 和 x=a ^q其中 0<=q< m 然后 z=a ^m-qk b ^2m+1

w ₂ =xyyz = a ^q a ^k a ^k a ^m-qk b ^2m+1

= a ^m+k b ^2m+1

但是对于任何 1<=k<=m 的值，这都不在 L 中

所以我们与抽引理有矛盾。所以，我们关于 L 是正则的假设是错误的。所以，L 不可能是正则的。