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