Tom Ritchford
1 min readApr 15, 2020

--

Quibble here — while your conclusion is right, the argument is wonky. Regular expressions are also equivalent to a “special class of Turing machines” and an efficient parsing algorithm for them does exist.

And in fact, parsing a context-sensitive language is not a Turing-complete problem — it can be parsed by a linear bounded nondeterministic Turing machine, so you never have to “wait infinite time for a result”.

The reason that CSLs can be inefficient to parse really has nothing to do with Turing machines at all, but that the decision problem for context-sensitive grammars is PSPACE-complete, which probably means that these problems cannot in general be solved in polynomial time.

--

--

No responses yet