"Licheng Fang" <[EMAIL PROTECTED]> writes: > I think if the backtrack is carried out in an exaustive way, we may say > the engine trys every possibility on the NFA, though it's not an NFA > itself.
The backtracking engine really can recognize languages that are not describable by classical regexps, by using backreferences, negation, etc. But exactly what it can do is nowhere near as well-understood as what classical regexps can do. I seem to remember that the fully general problem of recognizing regexps with negation is very hard, so the backtracking matcher either has to reject some strings it should really match, or else it has to bog down horribly with certain kinds of patterns. -- http://mail.python.org/mailman/listinfo/python-list
