4 ms·

Just to note additionally that the pumping lemma may only be used in that direction, not the other way. The language {1^x : x is not prime} is easily pumped wi

by maweki 5y ago

Just to note additionally that the pumping lemma may only be used in that direction, not the other way. The language {1^x : x is not prime} is easily pumped with x=z=1 and y=11. And regular languages are closed under complement. No pumping Lemma -> Not regular, Yeah Pumping Lemma -> Who knows

jwilk 5y ago
OK, you can trivially pump numbers with small factors. But what about the numbers that have all prime factors greater than the pumping length?
- 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 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.
- thaumasiotes 5y ago
  Just to tie everything up, if you have Dirichlet's theorem it's easy to show that {1^x: x not prime} is irregular through a "direct" proof by contradiction using the pumping lemma. 1. Assuming the language is regular, the pumping lemma tells us that it has a pumping length m, and all strings of length at least m can be divided into a prefix x, a suffix z, and a pumpable substring y, such that: 1a. |xz| < m 1b. |y| > 1 1c. The concatenation x y^n z remains in the language for all n. (In this case, this means that |xz| + n*|y| is nonprime for all nonnegative y.) 2. Consider the string c = 1^p², where p is a prime number greater than m[1]. 3. The pumping lemma will divide c into substrings x y z as described above. 4. Observe that |xz| < m < p and |y| = p² - |xz| 5. Dirichlet's theorem tells us that the arithmetic sequence {a + nd} contains infinitely many primes as long as a and d are coprime. Pumping our string c will generate strings with lengths belonging to the arithmetic sequence {|xz| + n(p² - |xz|)}. It remains to be shown that |xz| and (p² - |xz|) are coprime. 6. Observe that any number which divides both (p² - |xz|) and |xz| will also divide [(p² - |xz|) + |xz|] = p². 7. Since p is prime, the only divisors of p² are 1, p, and p². 8. Since |xz| < p, we can see that gcd(|xz|, (p² - |xz|)) = 1. This completes the proof; pumping c is guaranteed to produce not just one but infinitely many strings of prime length. [1] Euclid tells us that there is no greatest prime number, so we can guarantee the existence of such a p.
thaumasiotes 5y ago
Well, you can still easily base the proof on the pumping lemma: 1. The language {1^x: x prime} is not regular (as immediately shown by the pumping lemma). 2. The language {1^x: x not prime} is not regular (because it is the complement of {1^x: x prime}, and the complement of a regular language is regular). It follows that the pumping lemma does not apply to the language {1^x: x not prime}; just because the string 1111 can be divided that way doesn't mean all strings in the language can be so divided. > No pumping Lemma -> Not regular, Yeah Pumping Lemma -> Who knows This is incorrect; any language to which the pumping lemma for regular languages applies is a regular language.
- pxx 5y ago
  > This is incorrect; any language to which the pumping lemma for regular languages applies is a regular language No. The wikipedia page has an example of a pumpable but non-regular language. You just need to take the union of a pumpable language and a non-regular language in a way that you can pump elements of the second into elements of the first. The Wikipedia example is a little more formal, but we can do something like this. Consider, over the binary alphabet, L1 = {s : 00 or 11 is a (consecutive) substring of s} L2 = {(01)^n : n represents a Turing machine that halts on the empty tape} and L = L1 union L2. Identifying elements of L2 is "difficult" (this is where I'm not being formal, but clearly this is beyond the power of regular languages) and the elements of the two languages are disjoint (so I'm not playing some tricks with my language secretly being Σ*). Take the pumping length p = 3. There are only eight possibilities for the first three characters: 000,001,010,011 and their bitwise complements. In the first two cases pump on the last character as any string starting 00 is in the language L. In the third case pump on the middle character; either we get repeated 1s or the zeroes coalesce (note that this is exactly where we collapse L2 into L1 by pumping it). In the last case, pump on the first character; the repeated 1s ensure the final string is in L. For the complements just complement my constants. So any string s in L can be pumped. But it's clear that no DFA is going to recognize L2, a disjoint language from L1. I use the halting problem for L2 as a "hard problem" but you can just choose an arbitrary other language L2 = {(01)^n : n encodes an element of L*, where L* is not regular}.

by maweki 5y ago

jwilk 5y ago

OK, you can trivially pump numbers with small factors. But what about the numbers that have all prime factors greater than the pumping length?

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 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.
thaumasiotes 5y ago
Just to tie everything up, if you have Dirichlet's theorem it's easy to show that {1^x: x not prime} is irregular through a "direct" proof by contradiction using the pumping lemma. 1. Assuming the language is regular, the pumping lemma tells us that it has a pumping length m, and all strings of length at least m can be divided into a prefix x, a suffix z, and a pumpable substring y, such that: 1a. |xz| < m 1b. |y| > 1 1c. The concatenation x y^n z remains in the language for all n. (In this case, this means that |xz| + n*|y| is nonprime for all nonnegative y.) 2. Consider the string c = 1^p², where p is a prime number greater than m[1]. 3. The pumping lemma will divide c into substrings x y z as described above. 4. Observe that |xz| < m < p and |y| = p² - |xz| 5. Dirichlet's theorem tells us that the arithmetic sequence {a + nd} contains infinitely many primes as long as a and d are coprime. Pumping our string c will generate strings with lengths belonging to the arithmetic sequence {|xz| + n(p² - |xz|)}. It remains to be shown that |xz| and (p² - |xz|) are coprime. 6. Observe that any number which divides both (p² - |xz|) and |xz| will also divide [(p² - |xz|) + |xz|] = p². 7. Since p is prime, the only divisors of p² are 1, p, and p². 8. Since |xz| < p, we can see that gcd(|xz|, (p² - |xz|)) = 1. This completes the proof; pumping c is guaranteed to produce not just one but infinitely many strings of prime length. [1] Euclid tells us that there is no greatest prime number, so we can guarantee the existence of such a p.

thaumasiotes 5y ago

Well, you can still easily base the proof on the pumping lemma: 1. The language {1^x: x prime} is not regular (as immediately shown by the pumping lemma). 2. The language {1^x: x not prime} is not regular (because it is the complement of {1^x: x prime}, and the complement of a regular language is regular). It follows that the pumping lemma does not apply to the language {1^x: x not prime}; just because the string 1111 can be divided that way doesn't mean all strings in the language can be so divided. > No pumping Lemma -> Not regular, Yeah Pumping Lemma -> Who knows This is incorrect; any language to which the pumping lemma for regular languages applies is a regular language.

pxx 5y ago
> This is incorrect; any language to which the pumping lemma for regular languages applies is a regular language No. The wikipedia page has an example of a pumpable but non-regular language. You just need to take the union of a pumpable language and a non-regular language in a way that you can pump elements of the second into elements of the first. The Wikipedia example is a little more formal, but we can do something like this. Consider, over the binary alphabet, L1 = {s : 00 or 11 is a (consecutive) substring of s} L2 = {(01)^n : n represents a Turing machine that halts on the empty tape} and L = L1 union L2. Identifying elements of L2 is "difficult" (this is where I'm not being formal, but clearly this is beyond the power of regular languages) and the elements of the two languages are disjoint (so I'm not playing some tricks with my language secretly being Σ*). Take the pumping length p = 3. There are only eight possibilities for the first three characters: 000,001,010,011 and their bitwise complements. In the first two cases pump on the last character as any string starting 00 is in the language L. In the third case pump on the middle character; either we get repeated 1s or the zeroes coalesce (note that this is exactly where we collapse L2 into L1 by pumping it). In the last case, pump on the first character; the repeated 1s ensure the final string is in L. For the complements just complement my constants. So any string s in L can be pumped. But it's clear that no DFA is going to recognize L2, a disjoint language from L1. I use the halting problem for L2 as a "hard problem" but you can just choose an arbitrary other language L2 = {(01)^n : n encodes an element of L*, where L* is not regular}.