mozy contest: problem 1 PHP solution
levi at cold.org
Mon Nov 6 10:59:49 MST 2006
On Nov 6, 2006, at 10:50 AM, Daniel C. wrote:
> You realize that this problem has been proved Turing-incomplete right?
> There is no computer in the universe, and it is impossible to build
> one, that can decide every string in that language. I'm assuming they
> only gave you strings that were small enough to be decideable, but
> still, it's a bit funny that they picked this one.
Perhaps you are confusing Turing Machines with Finite State
Automata? You can match nested parentheses with a machine as simple
as a pushdown automata, which matches any context-free grammar. You
cannot, however, match them with a regular expression (in the CS
sense, not the perl one) which can only match regular grammars.
More information about the PLUG