The DTD is part of the 1.0 spec. The DTD is just a regular expression, and your document as a string to match. The validator is the interpreter that gives you

The DTD is part of the 1.0 spec. The DTD is just a regular expression, and your document as a string to match. The validator is the interpreter that gives you a yes/no answer for any problem you can represent in those terms. Actually... hmm. If you look closely at the entity replacement rules, the conditional inclusion entities, and the ability to include external dtd references, you may well be able to get full turing completeness.