Find minimum number of transformations to transform from input to target string Given that I have an input string, for example:  aab 
And I am given a target string, for example: bababa 
And then I am given a set of transformation rules. For example:

ab -&gt; bba
b -&gt; 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.

Thanks
EDIT

As noted by usul, my previous answer is too broad, so these are some additional notes with personal ideas (so it is now more like an extended comment, than an answer):

If the given grammar is context sensitive, the alphabet has size >= 2 and there are no limits in the number of transformations, then even the problem of deciding if the grammar generates the target string is undecidable. You can easily find a grammar that simulates a NTM; as pointed out by Jeffe Markov algorithms are Turing complete, so given a TM and a string w you can build a grammar and a source string that generate a target string iff TM halts on w. So finding the minimum is undecidable, too.

If you put a limit in the number of transformations (polynomial), then the problem of deciding if the grammar generates the target string is PSPACE complete, and the problem of finding the minimum number of transformations is surely harder.

If the number of transformations is fixed, I think that the the problem is NP complete (I've a fuzzy idea of a quick reduction from monotone NAE-3SAT)

I leave the previous answer below.

The problem of finding the smallest CFG grammar  that generates a given string (also known as Minimum Grammar Compression or MGC) is NP-complete (J. Storer, "NP-completeness results concerning data compression", 1977).

I think that the complexity of the problem when the alphabet is restricted to $\{0,1\}$ (2-MGC) is still unknown. 

If you switch to context sensitive grammars (LBAs) then you can look at resource-bounded Kolmogorov complexity. Unlike the unbouded Kolmogorov complexity, finding the smallest program that computes a given string is decidable, but we are obviously nearby intractability. There is a lot of reasearch on the subject (and many open problems); for example consider a binary string of length $2^n$ that represents the truth table of a boolean function $f$ and an integer $s$; the complexity of deciding if there is a boolen circuit of size at most $s$ that computes $f$ is unknown (probably not in $P$ but also unlikely to be NP-complete). Here it is a simple introduction and a very nice paper on the power of random strings.