问题标签 [pumping-lemma]

我看到了这个问题，并且很好奇引理是什么（维基百科没有太大帮助）。

我知道这基本上是一个理论证明，为了使一种语言进入某个类别，它必须是正确的，但除此之外，我真的不明白。

有人愿意尝试以非数学家/计算机科学博士可以理解的方式在相当细化的层面上解释它吗？

我的问题是：

令 L = { x in {a,b}* | x 具有相同数量的 a 和 b}

我知道这是一种上下文无关语言，因为我可以为它创建一个语法（e 是 epsilon）：

您还可以通过使用与常规语言相交的上下文无关语言是上下文无关的事实来证明它是上下文无关的。

由于它是一种上下文无关语言，根据 CFL 的抽运引理，任何长于抽运长度 p 的字符串都应该能够被抽运。但是，如果我选择字符串 s = a^pb^pa^pb^p，则无法抽出该字符串，因此该语言不应该是上下文无关的。

我哪里错了？

大多数 UNIX 正则表达式除了通常的 , 之外，还有**一个+反斜杠?*运算符，其中\1,\2,...匹配最后括号中的任何内容，例如*L=(a*)b\1*匹配（非正则）语言*a^n b a^n*。

一方面，这似乎非常强大，因为您可以创建(a*)b\1b\1以匹配*a^n b a^n b a^n*堆栈自动机甚至无法识别的语言。另一方面，我很确定*a^n b^n*不能这样表达。

我有两个问题：

1. 有没有关于这个语言家族的文献（UNIX-y 常规）。特别是，这些引理是否有一个版本？
2. 有人可以证明或反驳*a^n b^n*不能以这种方式表达的事情吗？

我有以下问题：

语言 L1 = {a^n * b^n : n>=0} 和 L2 = {b^n * a^n : n>=0} 是上下文无关语言，因此它们在 L1L2 下是封闭的，因此 L={a ^n * b^2n A^n : n>=0} 也必须是上下文无关的，因为它是由闭包属性生成的。

我必须证明这是否属实。所以我检查了 L 语言，我认为它不是上下文无关的，然后我还看到 L2 只是 L1 反转。

我是否必须检查 L1、L2 是否是确定性的？

我觉得在这里发布如此简单的问题就像一个白痴，但这个网站的知识库真是太棒了。感谢您的理解。

关于寻找正则表达式的最小泵送长度（关于正则语言的泵送引理）的问题：

正则表达式 R = 1011（在字母表 {0,1} 上）

不是这个字符串 ε（空字符串）和 1011 的唯一匹配项吗？

编辑-我一直在盯着太多的 kleene 明星。空字符串 ε 不是这种语言。

正则语言的属性表明，如果一种语言可以用有限自动机（或正则表达式）表示，那么它就是正则的，当然这个语言也可以用两者来表示。（而且这个问题显然让我相信语言是正常的）

但另一方面，抽水引理（非正式地）指出，所有常规语言都具有抽水长度，因此至少该长度的所有字符串都可以拆分为 xyz，其中 y 可以重复而不会影响结果。ε 不能按定义泵送，并且 1011 不能泵送（我不认为，这是问题）因为没有其他字符串匹配它，因此删除或添加 y 的实例将导致字符串不被接受/匹配。

我的逻辑错误在哪里？

第二次编辑-任何 p>4 的答案是否可以通过将 x 或 y 或 z 设置为 φ （空集）来抽取语言，当与任何东西连接时会导致空集？

我需要证明 A 不是上下文无关的。我猜我必须为此使用 Pumping Lemma，但是如何？

我有{a^i b^j c^k | i,j,k>=0 & i>j & j>k} 我开始假设m为我挑选一些的语言，例如一个字符串

然后将字符串拆分为不为空的字符串，(z =) uvwxy然后 当我选择一个“ ”时，我感到困惑。假设我选择然后我有： 而且我不完全确定从哪里开始，因为对我来说，看起来我可以选择该语言中的 vwx。vx#(vwx)<=mii=1uv^1wx^1y

有什么建议么？

我有一个关于常规语言的抽引引理的小问题 - 是否足以表明如果属于语言 L 的特定字符串无法抽出，那么该语言是不规则的？例如 - 如果我选择语言 L1 的形式为 a^nb^n (ab, aabb, aaabbb ...) 并且我表明字符串 aabb 不能被抽出并且仍然是 L1 的一部分，那么它是对我立即得出 L1 不规则的结论有效吗？

干杯。

我正在上自动机理论课，现在我们正在学习抽水引理。有一个练习题要求我们“设计一种语言 L，使得 L 和它的补码都没有无限的正则子集？” 但我不明白这个问题。什么是无限正则子集？我应该如何找到可以满足此要求的语言？

任何人都可以对这个问题有所了解吗？

谢谢！

在我的考试中，我应该写出所有的抽引引理条件。这正是我所做的：

一位朋友告诉我有一些错误，但我找不到它们......有人可以帮忙吗？有什么错误&为什么？