3 ms·
Think about what you're saying. You think 15 is an even number? maweki may be thinking that you can divide a string for pumping lemma purposes any way you plea
by thaumasiotes 5y ago
Think about what you're saying. You think 15 is an even number?
maweki may be thinking that you can divide a string for pumping lemma purposes any way you please. If that were true, you could show that all strings of nonprime length could be pumped while still retaining nonprime length:
1. |s| is composite, so |s| = km for some integers k and m
2. Choose the length of the pumpable substring y to be k. Then |xz| = s - k = k(m-1), and |x y^n z| = k(m-1) + kn = k(m + n - 1). This is composite, so the pumping is valid.
The problem, as jwillk has identified, is that the pumping lemma doesn't allow this. The language has a pumping length (traditionally m), and you have to divide your string into three substrings x y z such that all of the following are true:
1. |y| > 0
2. |xz| < m
3. x y^n z remains in the language for all n.
Condition (2) prevents us from using the maweki strategy.