Given two strings S and T of same length. Given a set of replacement rules, that find substring A in S and replace it with string B. A and B have the same length.

Is there a sequence of rule application, such that it make string S into string T?

I believe there is no better way to answer this than try every single rule in every single state. Which would be exponential time. But I don't know if there are better solutions to it.