Finding errors in pumping lemma conditions
In my exam, i was supposed to write all pumping lemma conditions. that exactly what i did :开发者_开发百科
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
- xyiz ∈ L, i ≥ 0
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.
精彩评论