问题标签 [pumping-lemma]

L = {a^ib^jc^k; i≠j 和 i≠k 和 j≠k}。

第一种方法：我尝试了两个不同的字符串来通过抽取引理来证明它，但它们都不正确。第一个 w = a^mb^m+1 c^m+2 和 m 是泵送长度。例如 w = uvxyz 的一种情况是 vxy in 是一部分。所以 w = a^mk a^kb^m+1 c^m+2 对于任何 i >=0 它必须在 L wi = a^mk a^ik b^m+1 c^m+2 中。我不能证明 a 的数量等于 b 的数量。

第二种方法：我将 L 转换为 6 种不同语言的并集 {a^ib^jc^k U a^ib^kc^j U a^jb^ic^k U a^jb^kc^i U a^kb^ic ^j U a^kb^jc^i ; 一世

我在使用上下文无关的抽引引理解决这个练习时遇到了一些麻烦。有人可以帮忙吗？

给定一个在字母 ∑ 上定义了 n 个状态的 DFA M，以及一个满足 |x|>n 的字符串 x∈L(M)，我必须证明 L(M) 是一种无限语言。

有什么方法可以使用抽水引理证明这一点？

如果我有这样的语言：

L1 = {a^128 b^na^n | n >= 0}

我必须证明它不是正则的，是否足以证明 b^na^n 不是正则的，因此整个表达式不是正则的，因为 a^128 是有限的？

我一直在观看很多关于如何证明这一点的视频，并且我得到了关于如何证明这一点的混合信息。

在矛盾的情况下，我得到了两种不同的方法，我想知道哪个是正确的。

例子：

L = {a^nb^n+1 c^n+1: n>=0}

一位消息人士说我可以假设该语言是上下文无关的，选择 u,v,x,y 的子字符串，同时保持这三个约束，即：

1. 对于所有 i>=0，uv^ixy^iz 都在 A 中
2. |维| > 0
3. |vxy|<= p

然后显示被抽出的字符串不在语言中，即使在保持 CFL 的约束的情况下也是如此。如果抽出的字符串不在语言中，那我怎么能表现出矛盾。

另一个消息来源说在选择 vxy 时必须遵循某些规则，即 vxy 必须跨越中点......如果你将字符串分成 5 部分并且不满足约束，那么仅此一项就证明了语言是不是节能灯。

基本上，哪种方法是正确的？划分u，v，x，y的规则是什么？

有很多关于pumpinglemma证明的例子，但我没有弄清楚这一点，有人可以帮忙吗？

L= { a^nb^nc^md^m : n >= 1, m >= 1 } U { a^nb^mc^md^n : n >= 1, m >= 1 }

我不太了解抽水引理，可以简单分解一下如何证明这样的事情。

我需要证明给定的语言不规则，这可以吗？

该语言 M={a^m a^l c b^(m+l)|m,l in N}使用字母 = {a,b,c}。

证明：

是还是不是？如果你能告诉我我的错误，我将非常感激

bin 是二进制中最短的数

bin(n)bin(2^(k+1) * n + 1)^R 上下文是否免费？

k,n 属于自然数。

我知道 bin(n)bin(n + 1)^R 是上下文无关的，但我不知道如何解决 bin(n)bin(2^(k+1) * n + 1)^R 。如果是上下文无关的，有人可以帮我建立上下文无关的语法吗？

我在哪里可以找到线性上下文无关语言抽取引理的证明？

我正在寻找特定于线性上下文无关语言的证明