Hacker News Reader

> 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.)

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.

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

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

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.

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.

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.

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.

> 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}.

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?

You would need a different proof (likely a much more complicated one) for n-ary primes.

https://math.stackexchange.com/questions/1232463/how-to-prov... has a proof for base 2. This method works for other bases too.

Nice!

this is why I love hackernews