问题标签 [pumping-lemma]

我最近有一个任务，要求我使用抽引引理来表明一种语言不规则，不幸的是得到了错误的答案。

证明语言是非常规的如下： L = {a ⁱ b ^j c ^k : i = j or j = k}

我给出的抽水引理的定义如下：

1. 对手选m
2. 我想选择 w 来反驳抽水引理。使用 m 选择字符串 w ∈ L 其中 |w| ≥米
3. 对手选择受约束的 w 分解。
4. 我尝试选择一个 i 以便抽出的字符串 w _i ∉ L。如果找到，则 L 不是正则

事实证明，这个主题对我来说非常难以理解，因此我感觉自己就像一个完整的空想，因此我将不胜感激详细解释我将如何正确应用抽水引理。

假设我有一种语言 L = {wxwR}，其中 wR 是 w 的倒数，w 和 x 的最小长度为 1，w 可以由 0 或 1 组成，而 x 只能由 1 组成。

我如何证明这种语言不规则？除了使用抽水引理之外，还有其他方法吗？如果使用抽引引理，我仍在弄清楚我应该为字符串 s=xyz 选择什么 x、y 和 z，如果您能给我任何提示，我将不胜感激。

谢谢！

嗨，我正在尝试为抽引引理做练习题。我需要证明语言 L = {w E 字母 a,b,c | w 中 bs 的数量是 cs 的两倍，bs 的数量是 cs 的两倍}

现在我创建了一个属于 L 的单词 w = a^4n * b^2n * c^n。我一直试图在计算中走得更远，但我不明白该怎么做。我如何找到 xyz 代表什么？我如何证明存在矛盾？我已经尝试了很长时间并且在互联网上到处寻找，但我真的很挣扎。

我试图证明语言 { w ϵ {a, b, c}* | n_a(w) < n_b(w) 和 n_a(w) < n_c(w) } 不是使用 Pumping Lemma 的 CFL。符号“n_a”表示“‘a’的数量”。

对于抽取引理，z = u(v^i)x(w^i)y, |vxw| <= 米, |vw| >= 1。

我选择使用字符串 z = (a^m)b^(m+1)c^(m+1) 来表明这不是 CFL。

但是，我陷入了以下情况。

假设'uvx'代表'z'的(a^m)部分，'w'代表'z'的(b^m)部分的开始，'y'代表'z'的其余部分。

现在抽水 i = 2，我们得到 z' = u(v^2)x(w^2)y = a^(m + |v|)b^(m + 1 + |w|)c^(m + 1）。

每当 |v| ≠ 0，我们看到这不在语言中，因为 n_a(z') 不小于 n_c(z')。但是，对于 |v| = 0，我们得到 z' = a^(m)b^(m + 1 + |w|)c^(m + 1)，这在语言中是。因此，用 i = 2 抽水是行不通的。这个对吗？

我尝试使用其他值“i”，但我仍然无法证明这种语言不是 CFL。我究竟做错了什么？这种语言实际上是上下文无关的吗？我应该使用完全不同的“z”字符串吗？

我需要这种语言的 DFA 和正则表达式。

我认为 DFA 是这样，但我得到的正则表达式是 ((aUb)a)*，我认为这是不正确的。

我正在努力解决以下问题。我应该使用抽引引理或常规语言闭包，但我无法为这两个问题提出解决方案。任何见解将不胜感激。谢谢。

对于以下每种语言，证明它是正则的或证明它是非常规的：

当涉及到数字 1 时，我的假设是给定语言的反面也必须是正则的。然后我可以使用抽水引理来证明它不是正则的，因此原始语言是非常规的。这会是一种有效的方法吗？

老实说，我不知道如何接近 2 号。

{a^pb^p; p 是素数}

{a^pb^p; p为素数，m为定数，m≥p≥0}

我如何证明这是否是常规语言/上下文无关语言（或不是）？

常规语言的抽吸长度与相关语言的抽吸长度有何关系。例如，如果 A :< B :< C 都是正则语言，k 是 B 的泵送长度，我们是否知道 A 和 C 的泵送长度？

当我们查看有限语言时，人们可能会天真地认为子语言具有较小的 (<=) 泵送长度。{a,ab,abc} :< {a,ab,abc,abcd} 的泵送长度分别为 4 <= 5。从集合中取出一个元素不能使其最长的单词更长。

另一方面，如果你看由两种语言的同步乘积形成的状态机，交集语言和并集语言具有相同的状态机结构，但不同之处在于交集的最终状态集是联盟的最终状态集。拥有更多的最终状态，可以使其更有可能通过状态机找到更短的路径。但相反，具有较少的最终状态使得状态机更有可能具有不可共同访问的状态，因此是可约的。

考试即将到来，教授希望包括这些信息。我了解引理是如何工作的，但我无法概念化“泵送”是如何发生在进出和多少次方面的。

我正在努力解决以下问题。我应该使用抽水引理。

证明 {a^nb^mc^min(n,m) | m,n >= 0 } 不是上下文无关的。