标签: pumping-lemma

我看到了这个问题,并对抽取引理是什么感到好奇(维基百科没有多大帮助).

我理解这基本上是一个理论证明,必须是真实的,以便语言在某个类中,但除此之外,我并没有真正得到它.

有人试图以非数学家/ comp sci博士学位理解的方式在相当精细的层面上解释它吗？

我试图理解在Pumping引理的每个应用中使用的这个"神奇"数字'n'是什么.经过几个小时的研究,我来到了以下网站:http://elvis.rowan.edu/~nlt/TheoryNotes/PumpingLemma.pdf

它指出

n是最长的字符串,没有循环.最大的n可以是s,但对某些特定语言来说可能更小.

根据我的理解,如果有一个语言L,那么L的泵浦长度是有限状态自动机中识别L的状态量.这是真的吗？

如果是,那么上面的最后一行究竟是什么意思"虽然某些特定语言可能会更小"？在我脑海里乱七八糟.有人可以把它弄清楚吗？

所以这不是关于泵浦引理及其工作原理,而是关于先决条件.

你可以阅读网络中的任何地方,常规语言必须通过抽取引理,但现在任何人都会谈论有限语言,它实际上是常规语言的一部分.

所以我们可能都是aggree,以下语言是有限语言,也是常规语言,但它肯定不会通过泵引理:

L = {'abc', 'defghi'}

请告诉我,如果没有人写它或为什么我们错了 - 甚至没有.

我正在学习问题中的引理之间的区别.我能找到的每个引用都使用了这个例子:

{(a^i)(b^j)(c^k)(d^l) : i = 0 or j = k = l}

显示两者之间的差异.我可以找到一个使用常规引理来"反驳"它的例子.

选择w = uvxyz,st | vy | > 0,| vxy | <= p.假设w包含相等数量的b,c,d's.

我选择了:

u,v,x = ?
y = (the string of a's)
z = (the rest of the string w)

抽取y只会增加a的数量,如果| b | = | c | = | d | 起初,它现在还会.

(类似的论据,如果w没有a.那么只需抽出你想要的任何东西.)

我的问题是,奥格登的引理如何改变这一策略？"标记"有什么作用？

谢谢!

大多数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*不能以这种方式表达吗？

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

   z = a^m b^(m-1) c^(m-2)

然后,将字符串分成(z =) uvwxy,这样vx是不是空的,#(vwx)<=m 然后,当我来挑一个" i"我感到困惑.说我选择i=1然后我有: uv^1wx^1y而且我不完全确定从哪里开始因为对我来说看起来我可以选择一种语言中的vwx.

有什么建议？

在使用泵浦引理检查给定语言是否规则时,我有点困惑.

假设我们必须检查是否:

L. 语言是否接受0常规或非常规的语言？

我们知道这是常规的,因为我们可以为L构建DFA.但我想用抽取引理来证明这一点.

现在假设,我拿一个字符串w= "0000":

现在,将分字符串x = 0,y = 0和z = 00.现在应用泵浦引理i = 2,我将得到字符串"00000",这是我的语言不存在所以通过引入引理证明语言不规则.但它被DFA接受了吗？

任何帮助将不胜感激,
谢谢

我需要一些泵浦引理问题的帮助.

L = { {a,b,c}* | #a(L) < #b(L) < #c(L) }

这是我到目前为止所得到的:

y = uvw is the string from the pumping lemma.

我让y = abbc ^ n,n是泵浦引理的长度.y在L中,因为a:s的数量小于b:s的数量,并且b:s的数量小于c:s的数量.

我让u = a,v = bb和w = c ^ n.| UV | <y,如抽水引理中所述.如果我"抽"(bb)^ 2然后我得到

y = abbbbc^n which violates the rule #b(L) < #c(L).

这是正确的吗 ？我是在"正确的道路上"吗？

谢谢

使用泵引理,我们可以很容易地证明,语言L1 = {WcW^R|W ? {a,b}*}是不是正规的语言.(字母是{a,b,c}; W ^ R代表反向字符串W)

然而,如果我们替换字符c用"x"(x ? {a,b}+),比如说L2 = {WxW^R| x, W ? {a,b}^+},则L2 是一个普通的语言.

你能给我一些想法吗？

我试图通过 Pumping Lemma 证明以下语言不是正则的。但我不确定我是否做得正确。

{L = a ^{2 n} | n>= 0 }

到目前为止，我所做的如下：

s = a ^{2 p}

x = a ^{2 i}

y = a ^{2 j}

z = a ^{2 p-ij}

因此 xy ² z = a ^{2 p+j}

这意味着 a ^{2 p+j} > a ^{2 p} ，使语言不规则

我做得对吗？还是我有什么问题？