Re:A regular expression to check for prime numbers
by _delirium on Sunday July 04, 2010 @06:07PM
(#1486502)
My theory-of-computation prof a few years ago was of the opinion that CS-theory people should stop making that argument, and go with the standard usage of "regular expression" being a particular syntax for writing matching statements, of which PCRE syntax is the most popular, and use "regular language" if they want the CS-theory meaning.
[ Parent
| on HN ]
Re:A regular expression to check for prime numbers
by philh on Sunday July 04, 2010 @06:35PM
(#1486554)
I don't disagree. But the programmers have "regexes" which refers unambiguously to their type of "regular expression"; there's no good equivalent for a CS theorist. (A regular language is not a regular expression, just like the set of prime numbers is not a test for primality.)
Re:A regular expression to check for prime numbers
by baddox on Monday July 05, 2010 @01:39AM
(#1487389)
The problem with that is that it ruins the excitement from hearing that "a regular expression can solve problem X." I believe most regex implementations are actually Turing complete, so it's no surprise that a problem can be solved with them. But that's just another CS-theory person argument.
Re:A regular expression to check for prime numbers
by _delirium on Monday July 05, 2010 @04:23AM
(#1487682)
Yeah, I see regexes as more of a question of expression, in the pragmatic human programmer sense, rather than formal expressibility. Some things are natural and easy to write using regexes, and some are much better done some other way, but I'm not sure the Chomsky hierarchy shows where that boundary is.