4 ms·

you can use the pumping lemma (https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_lang...

by pxx 5y ago

you can use the pumping lemma (https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_lang...) to do this proof trivially. it'll look something like {1^x : x is prime} is not a regular language. suppose it is a regular language. then by the pumping lemma there exists a p such that every string of length at least p can be written as w = xyz, where |y| >= 1, |xy| <= p [not an important observation for this proof], and we can "pump" a new string w' = xy^nz (for any n > 0) and have w' remain in L. let p' be the prime immediately above p. then the string w = 1^p' is in the language L and must be "pumpable" for some N = |y| > 0. Choose the number of times we "pump" (n in the expression xy^nz) to be p'. Then that would imply w' = 1^(p' + p' * N) is in the language L, a contradiction, as p' + p' * N has factors p' and (1 + N). Note we can also use the CFL pumping lemma to prove that this particular language is not context-free either; if we choose s = uvwxy, we can still just pump p' times; the new string just is of size p' * (1 + |v| + |x|), and |v| + |x| > 0.

colanderman 5y ago
Fantastic! It's been 15 years since I've had to do those proofs, I'll use your proof to refresh my memory how they work.
thaumasiotes 5y ago
> we can "pump" a new string w' = xy^nz (for any n > 0) While this is certainly true, I would prefer to note that n ≥ 0. n > 0 is just a special case of that. (You can see clearly that 0 repetitions will always be valid by considering the proof of the pumping lemma: since a regular expression is recognized by a finite state machine, the only way to recognize a string of length exceeding the (finite!) number of states in the machine is to visit some states more than once, which means traveling around a cycle in the state graph. The 'pumpable substring' of the pumping lemma is a path through such a cycle, and repeating it zero times corresponds to traveling around the cycle zero times. The rest of the path is just as valid as always.)
Capira 5y ago
this is why I love hackernews
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.
kevinventullo 5y ago
It’s been a while since I took Theory of Computation. Does this imply that primes in binary or n-ary are also not regular?
- jwilk 5y ago
  You would need a different proof (likely a much more complicated one) for n-ary primes.
  - jwilk 5y ago
    https://math.stackexchange.com/questions/1232463/how-to-prove-the-language-of-all-binary-numbers-that-are-prime-is-nonregular-usi https://math.stackexchange.com/questions/1232463/how-to-prov... has a proof for base 2. This method works for other bases too.
    - kevinventullo 5y ago
      Nice!

by pxx 5y ago

colanderman 5y ago

Fantastic! It's been 15 years since I've had to do those proofs, I'll use your proof to refresh my memory how they work.

thaumasiotes 5y ago

> we can "pump" a new string w' = xy^nz (for any n > 0) While this is certainly true, I would prefer to note that n ≥ 0. n > 0 is just a special case of that. (You can see clearly that 0 repetitions will always be valid by considering the proof of the pumping lemma: since a regular expression is recognized by a finite state machine, the only way to recognize a string of length exceeding the (finite!) number of states in the machine is to visit some states more than once, which means traveling around a cycle in the state graph. The 'pumpable substring' of the pumping lemma is a path through such a cycle, and repeating it zero times corresponds to traveling around the cycle zero times. The rest of the path is just as valid as always.)

Capira 5y ago

this is why I love hackernews

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.

kevinventullo 5y ago

It’s been a while since I took Theory of Computation. Does this imply that primes in binary or n-ary are also not regular?

jwilk 5y ago
You would need a different proof (likely a much more complicated one) for n-ary primes.
- jwilk 5y ago
  https://math.stackexchange.com/questions/1232463/how-to-prove-the-language-of-all-binary-numbers-that-are-prime-is-nonregular-usi https://math.stackexchange.com/questions/1232463/how-to-prov... has a proof for base 2. This method works for other bases too.
  - kevinventullo 5y ago
    Nice!