问题标签 [pumping-lemma]

我有一个编译器问题。

确定是否 {(ab)^n | n >= 0} 是常规语言吗？

但我可以画出它的 NFA。但是如果我使用抽引引理，我会得到一个矛盾的答案。

谁能帮我 ？

让L = {a^f(m) | m >= 1 }wheref: Z^+ -> Z^+是单调递增的，并遵守对于其中的所有元素n都有Z^+属于m这样Z^+的f(m+1) - f(m) >= n。

是否可以证明 L 是正则语言？

我试图使用抽水引理证明以下语言不规则

L= { a^ib^j | i^2 > j}

对此有什么建议吗？我完全被困住了。

谢谢。

我在谷歌上搜索了上下文敏感的引理，它似乎只产生上下文无关语言的结果。

抽引理只允许证明一种语言是上下文无关的吗？并且不区分上下文？

知道怎么做吗？

我在测试中弄错了这个问题，想知道是否有人可以解释它，显示得出结论所采取的步骤。任何帮助，将不胜感激。

在 L_neq = {0^i1^j | 的 PL 证明中 i < j} 给定一个 m-state DFA，有人选择字符串 0^(m/2)1^(m/2+1)。然后他们选择 y = 0 并表明通过抽水，我们可以到达 L_neq 之外的字符串 0^(m/2+1)1^(m/2+1)。这个证明正确吗？为什么或者为什么不？

此外，如果这个证明是错误的，请写下一个正确的证明。

谢谢

我在这方面考虑了很长时间，但仍然无法在这方面走得太远。第一步很容易考虑任何形式为 o^M 的语言，其中 M 是大于我们对手给出的素数（假设是 n）。我无法弄清楚我们如何从这里证明无论我们的对手如何打破字符串，我们总是可以泵送它以表明它不属于上下文无关语言类（因此不属于常规语言）。

PS：这不是作业问题。我已经完成了这门课程。只是想解决它，因为我在课程期间无法解决它。

语言 L 满足常规语言的抽引引理和上下文无关语言的抽引引理。以下关于 L 的陈述哪些是正确的？

A.L 必然是一种常规语言。

B. L 必须是 CFL 但不是正则。

C. L 必然是非常规的。

D. 无

我会清楚我怀疑的地方。如果 L 满足正则语言的抽引引理，那么它不一定是正则的。与无上下文相同。所以它可以是常规的或非常规的。节能灯或非节能灯。给出的答案是B，但在我看来应该是D。谁能指出我遗漏了什么。

我们对正则语言使用抽引引理来找出一种语言是否正则。作业中有一个问题，我不知道如何将泵引理应用到语言上。

$ 只是用于拆分 a 和 b 的常数。

还有一种语言是这样的：

我知道现在没有什么可以拆分 a 和 b 并且不可能对 a 中的零个数和 b 中的个数做出假设，对吧？还是我弄错了？

我们如何将抽引引理应用于这些语言以证明它们是正则与否？

我有一个引理问题，我完全坚持...

L = {w ∈ {a, b, c}∗ : na (w) < nb (w) < nc (w)}

是不是节能灯？

我要求它不是 CFL，因为只有一个堆栈来记住所有这些条件是不够的。你可以记住 na (w) < nb (w) 或 na (w)< nc (w),nb (w) < nc (w) 但不是 na (w) < nb (w) < nc (w)。另外，我认为如果语言是 a^pb^2pc^3p 而不是我打气 |vy| p 次 L 不是 CF 但是你有可能抽 p 次吗？

或者对解决方案有什么想法？

以下语言上下文是免费的吗？

我试图想出一个上下文无关的语法来生成它，但我做不到，所以我假设它不是上下文无关的。至于我的反证法：

假设 L 是上下文无关的，

令 p 是由泵引理给出的常数，

选择字符串 S = a^pb^pc^pd^p 其中 S = uvwxy

作为 |vwx| <= p，那么 vwx 最多可以包含两个不同的符号：

情况 a) vwx 仅包含单一类型的符号，因此 uv^2wx^2y 将导致 i+s != k+r

案例 b) vwx 包含两种类型的符号：

i) vwx 由 b 和 c 组成，因此 uv^2wx^2y 将导致 i+s != k+r

现在我的问题是，如果 vwx 由 a's 和 b's，或 c's 和 d's 组成，那么泵送它们不会破坏语言，因为 i 和 k 或 s 和 r 可能会一致增加，导致 i+s == k +r。

我做错了什么还是这是一种上下文无关的语言？