show that L = { a^(pq) : p and q are primes } is not regular
Name:
Anonymous2011-04-15 6:46
The truth of the statement is obvious, so the point of the exercise is to execute the proof flawlessly.
Suppose we have a DFA with n states. Let's feed it first n + 1 primes (i.e. sequences a^p where p is prime), separately. So we'll have at least one state that is produced in at least two ways. I.e. state X = S(a^p1) = S(a^p2) for some different primes p1 and p2. Let's say p1 < p2. Then we have the sequence a^(p2 - p1) that takes DFA from this state X to itself. Let k = p2 - p1, note that k > 0 and that's all we need to know about it.
Also, we know that X(a^p1) is an accepting state (it's a^pq where p = p1 and q = 2). So we can first take a^p1, then a^(m * k) for any natural m, then a^p1 again, and that is supposed to be an accepting state. Now now we need to find an m which makes p1 + m * k + p1 == p * q where at least one of p and q is not prime. Let's use m = m' * p1, then we have p1 * (2 + m' * k). Here p = p1 which is prime, and q = (2 + m' * k), and we need to show that for any k can find such m' that q = 2 + m' * k is not prime. For example, m' = 2 would work.