开发者

Finding errors in pumping lemma conditions

In my exam, i was supposed to write all pumping lemma conditions. that exactly what i did :开发者_开发百科

Finding errors in pumping lemma conditions

a friend told me that there is some errors but i can't find them... Can some one help please ? what are the errors & why ?


If I remember correctly, the conditions need to be as follows:

  • |xy| ≤ p
  • |y| ≥ 1
  • xyizL, i0

So y must not be empty and y can be repeated zero or more times.


You're almost right, but the pumping lemma requires that |xy| ≤ p, not |xz| ≤ p. The idea is that the string is split into some initialization (x), steady-state (y), and tail (z) and that the initialization plus steady state logic is some length.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜