Regular Expression for Prime Numbers (or How I came to fail at them, and love the bomb)

[Henry]

>
> > There's no finite state machine involved here, since this isn't a
> > regular expression in the strictest sense of the term---it doesn't
> > translate to a finite state machine, since backreferences are
> > involved.
> >
> > Mark
>
>
> What is it?
>


The language of strings of 1s whose length is prime is not regular, so can't
be recognised by a finite state automata. Essentially you still need some
memory to remember where you've got up to in the factoring process, and the
amount of memory is dependent on the length of the string (more factors to
try), so it can't be done with finite storage.

Sketch proof that prime is not regular:

If P = {1^p | p is prime} is regular, then there exists x, z and y s.t. x.y^
k.z is in P for all k >= 0.

Assume l = |x.z| >= 2 (smaller than 2 has direct counterexamples, left as
easy exercise!). Consider w = x.y^l.z Then l | |w|. But since l >= 2, that
means that |w| is not prime. Therefore w is not in P, contradicting our
assumption.

Sorry for slightly OT post :)

Henry
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20080214/00cea18a/attachment-0001.html>