tag:blogger.com,1999:blog-11295132.post1142052214286657429..comments2009-12-18T17:45:24.966-08:00sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-11295132.post-41610881615362737652007-02-19T17:15:00.000-08:002007-02-19T17:15:00.000-08:00This is a fun problem. Thanks!<BR/><BR/>Here's my regexp. I wrote an automaton first and then sort of hand-crafted the regexp from it rather than went by Kleene's theorem (to make it less ugly and more economical):<BR/><BR/><BR/>^(0|1((0(01|111)*(00|110))*(1|0(01|111)*10))<BR/>(01*0(1(10|000)*(11|0(000)*01))*<BR/>(0|1(10|000)*0(000)*1))*1)*$Anatolyhttp://www.lovestwell.orgnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-87040718492441237752007-02-19T11:00:00.000-08:002007-02-19T11:00:00.000-08:00Anonymous,<BR/><BR/>Yup, it was reversed. I've already fixed that once, I must have accidentally undone the changes in my text edit. Thanks for alerting me! Anyway, it's now fixed.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-46383804951378191012007-02-19T10:52:00.000-08:002007-02-19T10:52:00.000-08:00Anonymous,<BR/><BR/>I don't have time to check right now yet but that looks like a regexp for spotting multiples of two written backwards. I wrote two versions of this code and I think I may have posted the backwards one. Oops. that's embarassing! I'll check and fix later :-)sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-78761187518562480592007-02-19T10:07:00.000-08:002007-02-19T10:07:00.000-08:00This doesn't work for 2?<BR/><BR/>% runhaskell mod.lhs<BR/>^\(0\|01*1\)*$<BR/>% grep '^\(0\|01*1\)*$'<BR/>0<BR/>0<BR/>10<BR/>^D<BR/>%Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-42293021916132066352007-02-18T18:10:00.000-08:002007-02-18T18:10:00.000-08:00What you say is true. But that doesn't detract from having solved the problem I set myself. Now Perl regular expressions might be different, I think you may be able to directly embed arithmetical expressions in those.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-52262117540390101872007-02-18T16:36:00.000-08:002007-02-18T16:36:00.000-08:00(I think my previous comment disappeared during submission)<BR/><BR/>nitpick<BR/>doesn't grep accept a superset of regular languages, because of the ability to use the \1 operator ? <BR/><BR/>/nitpickSureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-82717703361009018142007-02-18T16:34:00.000-08:002007-02-18T16:34:00.000-08:00If I may nitpick (and this is not to detract from your wonderful articles), what grep accepts is a superset of regular languages, since it can match things like (.*)(\1) which are strings of the form ww<BR/><BR/>or am I mistaken about grep.Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.com