Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 -> 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.


share|cite|improve this question
You could use a standard search algorithm like $A^*$. Can you be more specific about these rules? Are they context-free? – usul Feb 22 '13 at 22:48
What do you mean by context-free rules? All I am given are those rules. From a particular string it converts to another string. I fail to see how would I transform the input using the rules... – Hommer Smith Feb 22 '13 at 22:54
Well, for instance, the decision problem of whether a string can be parsed by a given context-sensitive grammar is PSPACE-complete. That seems to be a special case of your problem unless you have further restrictions (although I guess from your example that it's not context-free). – usul Feb 22 '13 at 23:07
There are no other restrictions than the ones I have written. I have been looking around the web to see any similar problems so I can have a base start, but no luck :( – Hommer Smith Feb 22 '13 at 23:16
This looks similar to Markov algorithms and tag systems, which are undecidable. – Jeffε Feb 23 '13 at 2:32


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.

share|cite|improve this answer
My understanding of the question seems to be backward from yours. As I understand it, the grammar is given and our task is to find the smallest parse tree. Right? – usul Feb 23 '13 at 4:13

I think the question is not yet quite precise, but let me give a couple ways it could be made precise and an answer for each.

1) We are given an "input string" $s$, an "output string" $t$, a set of pairs $F = \{(a,b) : \text{$a$ and $b$ are strings}\}$, and an integer $k$. The question is if there exists a sequence of pairs $(a_1,b_1),\dots,(a_n,b_n)$ such that: (1) each $(a_i,b_i) \in F$; (2) $a_1 = s$; (3) $b_n = t$; (4) for each $2 \leq i \leq n$, $a_i = b_{i-1}$; (5) $1 \leq n \leq k$.

In English, the $(a_i,b_i) \in F$ are "transformations" taking an input string to an output string, and we want to know if there is a length-$k$ or shorter sequence of transformations turning the input into the output.

This can be solved in polynomial time by Dijkstra's algorithm for shortest paths. Make $s, t$, each $a_i$, and each $b_i$ nodes in a graph, drawing a directed edge of length $1$ between $a_i$ and $b_i$ for each $(a_i,b_i) \in F$. There is a length-$k$ transformation of $s$ to $t$ if and only if there is a path of length $k$ between them in the graph.

2) We are given an input string, output string, and context-free grammar, and asked if the grammar generates the output string from the input string in a parse tree of $k$ or fewer nodes. In this case, the decision problem of whether any derivation exists can be solved in polynomial time but I am not sure about the problem of smallest derivation.

3) Same question but for a context-sensitive grammar. In this case, the decision problem of whether there exists a derivation at all is PSPACE-complete. I am not sure about complexity of finding a shortest derivation.

4) Same question but for an unrestricted grammar. In this case, even the question of whether there exists a derivation is undecidable.

share|cite|improve this answer
While I agree this can be solved with Djikstra's, it's not obvious to me that it's polynomial in the length of the input. – SamM Feb 23 '13 at 7:23
@SamM I think if we are given the transformation rules encoded as pairs as I assumed above, then I think it is polynomial since the number of vertices in the graph is $2n+2$ for $n$ pairs. If we are given a function (e.g., circuit) that computes the output given the input, then I agree that could be very difficult. It seems reminiscent of PPAD, except that a path is not guaranteed to exist... – usul Feb 23 '13 at 7:52
Just to clarify. It is not restricted to just a and b. The input string can have many characters. Also, there can be more than 2 rules. – Hommer Smith Feb 23 '13 at 8:41
Also, it is important to notice that I am not given any 'k'. I need to find the shortest. – Hommer Smith Feb 23 '13 at 9:23
As the answer states - the general problem you describe is undecidable. It is easy to reduce the word problem for TMs to this - the rules encode legal configuration transitions of the TM, and the input and output words represent the initial and final configuration of the TM. – Shaull Feb 23 '13 at 9:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.