No. This won't work because the time cost of primality testing is too high (cubic in the number of binary digits?), and checking if a string satisfies a regular expression takes only linear time. Since cubic is bigger than linear, this won't work. Too good to be true!
Not a proof, but a rule of thumb. No need to even use the pumping lemma.
This is just a conjecture, though.
> No need to even use the pumping lemma.
But it's really easy to prove this with the pumping lemma. This could be the first problem in a textbook section that introduces the pumping lemma. It would be difficult to come up with a language for which the pumping lemma disproof was more obvious.
-----
(1) a^n b^n
The pumping lemma tells us that for some string in this language, we can divide the string into three substrings x y z such that x y^n z remains in the language for all n.
There are two cases:
(1)(a) The number of 'a' characters in y does not equal the number of 'b' characters. In this case, pumping y will violate the constraint that a string in the language must have an equal number of 'a's and 'b's.
(1)(b) y consists of k 'a's followed by k 'b's for some k > 0. In this case, pumping it will violate the constraint that for every string in this language, each 'a' character must precede every 'b' character.
Thus, the language a^n b^n is not regular.
-----
(2) a^n, where n is prime
The pumping lemma tells us that for some string in this language, we can divide the string into three substrings x y z such that x y^n z remains in the language for all n. [same as above]
But the string x y^|xz| z has length |xz| + |y|*|xz|, which is not prime.
Thus, the language a^n (where n is prime) is not regular.
-----
Which of those was easier?
-> there exists a integer N such that pumping lemma holds for any w in L longer than L. (That is we can divide w into xyz and pump y, where |xy| ≤ n, and y is nonempty).
-> now consider a^N b^N, we cant divide it into xyz such that we can pump y and w still remains in a^n b^n.
So it actually 'works', it's just slower.