mozy contest: problem 1 PHP solution

[Levi Pearson]

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.

		--Levi