There's no halting problem involved here. All you need is to compute if the intersection of ^xy1d
and [^d]d2$
in non-empty.
I can't give you an algorithm here, but here are two discussions of a method to generate the intersection without resorting the construction of a DFA:
And then there's RAGEL
which can compute the intersection of regular expressions too.
UPDATE: I just tried out Ragel with OP's regexp. Ragel can generate a "dot" file for graphviz from the resulting state machine, which is terrific. The intersection of the OP's regexp looks like this in Ragel syntax:
('xy1' digit any*) & (any* ^digit digit '2')
and has the following state machine:
While the empty intersection:
('xy1' digit any*) & ('q' any* ^digit digit '2')
looks like this:
So if all else fails, then you can still have Ragel compute the intersection and check if it outputs the empty state machine, by comparing the generated "dot" file.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…