Given that I have an input string, for example:
And I am given a target string, for example:
And then I am given a set of transformation rules. For example:
ab -> bba b -> ba
There can be N rules.
The characters for the input and output string don't have to be just a and b, they can be any characters.
How could I do an algorithm that would find the minimum number of transformations that would need to be applied in the input string to get the target string.
In this example, for example, the number would be 3. Because we would do:
1 - Apply rule 1 (abba) 2 - Apply rule 1 again (bbaba) 3 - Apply rule 2 (bababa)
It could happen that given an input and a target, there is no solution and that should be noticed too.
Also, it can be that the target string is shorter than the input string.
I am pretty much lost in strategies on doing this. It comes to my mind creating an automata but I am not sure how would I apply in this situation. I think is an interesting problem and I have been researching online, but all I can find is transformations given rules, but not how to ensure it's a minimum.