Check if a string substitution rule will ever generate another string.
- by Mgccl
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.