Здравствуйте, dilmah, Вы писали:

D>каждому регэкспу соответствует конечный автомат.
D>Можно взять произведение этих автоматов (состояние нового автомата это пара состояний, пара (a,b) переходит в (x,y), если a->x и b->y)
D>И посмотреть достижимо ли в этом автомате конечное состояние (фактически есть ли путь в нем как в графе).

данный путь решения не приемлем с практической точки зрения, я бы сказал он "академический",
даже несложному выражению будет соответствовать конечный автомат с огромным числом состояний, для вычисления которого требуется ресурсы...