4 ms·
The above proof is just stating that all nonprimes >= 4 are even, and therefore can be pumped -- so contradiction by pumping lemma does not apply.
by colanderman 5y ago
The above proof is just stating that all nonprimes >= 4 are even, and therefore can be pumped -- so contradiction by pumping lemma does not apply.
- thaumasiotes 5y agoThink 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.