<p><strong>EDIT</strong></p>

<p>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):</p>

<p>If the given grammar is context sensitive, the alphabet has size >= 2 and <em>there are no limits in the number of transformations</em>, 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.</p>

<p>If you put a <em>limit in the number of transformations (polynomial)</em>, 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.</p>

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

<p>I leave the previous answer below.</p>

<p>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).</p>

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

<p>If you switch to context sensitive grammars (LBAs) then you can look at <em>resource-bounded Kolmogorov complexity</em>. 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 href="http://people.cs.uchicago.edu/~fortnow/papers/quaderni.pdf" rel="nofollow">a simple introduction</a> and a very nice paper on the <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.16.9225&amp;rep=rep1&amp;type=pdf" rel="nofollow">power of random strings</a>.</p>

CC BY-SA 3.0
2013-02-23T04:13:10.677Z
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
CC BY-SA 3.0
2013-02-23T00:40:26.647Z
2013-02-23T10:41:58.960Z
2013-02-23T10:41:58.960Z
Marzio De Biasi
<p>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.</p>

<hr>

<p>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$.</p>

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

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

<hr>

<p>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 <a href="http://en.wikipedia.org/wiki/CYK_algorithm" rel="nofollow">can be solved in polynomial time</a> but I am not sure about the problem of smallest derivation.</p>

<hr>

<p>3) Same question but for a <a href="http://en.wikipedia.org/wiki/Context-sensitive_grammar" rel="nofollow">context-sensitive grammar</a>. 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.</p>

<hr>

<p>4) Same question but for an <a href="http://en.wikipedia.org/wiki/Unrestricted_grammar" rel="nofollow">unrestricted grammar</a>. In this case, even the question of whether there exists a derivation is undecidable.</p>

CC BY-SA 3.0
2013-02-23T07:23:43.993Z
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
CC BY-SA 3.0
2013-02-23T07:52:14.887Z
@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](http://en.wikipedia.org/wiki/PPAD_\(complexity\)), except that a path is not guaranteed to exist...
usul
CC BY-SA 3.0
2013-02-23T08:41:57.083Z
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
CC BY-SA 3.0
2013-02-23T09:23:05.893Z
Also, it is important to notice that I am not given any 'k'. I need to find the shortest.
Hommer Smith
CC BY-SA 3.0
2013-02-23T09:39:21.830Z
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
CC BY-SA 3.0
2013-02-23T10:13:58.633Z
@HommerSmith You are misunderstanding my notation (the choice of $a$ and $b$ was misleading, sorry!). I am using $a$ and $b$ to stand for arbitrary strings. I am encoding a rule as a pair $(a,b)$ where the string $a$ is transformed into the string $b$, and I am allowing the input to contain an arbitrary number of rules. Also, if we have an answer to the decision problem given a number $k$, we will probably have an answer of how to find the shortest. For example Dijkstra's finds the shortest path. Hope that is more clear?
usul
CC BY-SA 3.0
2013-02-23T10:18:36.470Z
Oh ok...I think I get it now. But with your approach, I would be able to do N transformations and I would not know when to stop. Imagine input 'a', desired output 'b', and we have a transformation that looks like 'a -> ab'. How can I know when to stop doing transformations?
Hommer Smith
CC BY-SA 3.0
2013-02-23T16:58:09.427Z
@HommerSmith So here's where I'm confused. Say your only transformation is 'a -> ab'. On input 'a', is this legal: 'a -> ab -> abb -> abbb -> ...'? If so, then you have a grammar and are in case 2,3, or 4 above. If not, then you know when to stop because there are only so many possible strings you can get to before you would start cycling. (The number of such strings is 2 times the number of transformations, because you have the input and output of each transformation.) See [breadth-first search](http://en.wikipedia.org/wiki/Breadth-first_search) or Dijkstra's algorithm.
usul
CC BY-SA 3.0
2013-02-23T17:28:10.127Z
Yes, that would be legal. On first iteration you would get ab, then you would do abb, then...
Hommer Smith
CC BY-SA 3.0
2013-02-23T20:08:34.783Z
@HommerSmith OK, then you are in case 2, 3, or 4 above depending on what types of rules you allow.
usul
CC BY-SA 3.0
2013-02-23T04:41:40.950Z
2013-02-23T20:07:40.603Z
2013-02-23T20:07:40.603Z
usul
<p>Given that I have an <strong>input</strong> string, for example:  <code>aab</code> <br>
And I am given a <strong>target</strong> string, for example: <code>bababa</code> <br>
And then I am given a set of transformation rules. For example:</p>

<pre><code>ab -&gt; bba
b -&gt; ba
</code></pre>

<p>There can be N rules. <br>
The characters for the input and output string don't have to be just a and b, they can be any characters.</p>

<p>How could I do an algorithm that would find the <strong>minimum</strong> number of transformations that would need to be applied in the input string to get the target string.</p>

<p>In this example, for example, the number would be 3.  Because we would do:</p>

<pre><code>1 - Apply rule 1 (abba)
2 - Apply rule 1 again (bbaba)
3 - Apply rule 2 (bababa)
</code></pre>

<p>It could happen that given an input and a target, there is no solution and that should be noticed too.</p>

<p>Also, it can be that the target string is shorter than the input string.</p>

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

<p>Thanks</p>

CC BY-SA 3.0
2013-02-22T22:48:03.190Z
You could use a standard search algorithm like $A^*$. Can you be more specific about these rules? Are they context-free?
usul
CC BY-SA 3.0
2013-02-22T22:54:56.723Z
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
CC BY-SA 3.0
2013-02-22T23:07:40.037Z
Well, for instance, the decision problem of whether a string can be parsed by a given [context-sensitive grammar](http://en.wikipedia.org/wiki/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
CC BY-SA 3.0
2013-02-22T23:16:21.357Z
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
CC BY-SA 3.0
2013-02-23T02:32:51.483Z
This looks similar to [Markov algorithms](http://en.wikipedia.org/wiki/Markov_algorithm) and [tag systems](http://en.wikipedia.org/wiki/Tag_system), which are **undecidable**.
Jeffε
CC BY-SA 3.0
2013-02-23T04:20:21.340Z
@JɛﬀE yes, and the closely related [unrestricted grammars] are undecidable as well. But it seems that the rules here have more structure that we can exploit....
usul
<graph-theory><graph-algorithms><automata-theory><grammars>
Find minimum number of transformations to transform from input to target string
Hommer Smith
# Find minimum number of transformations to transform from input to target string

(Asked by: username_0 on 2013-02-22)

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

**Tags:** graph-theory, graph-algorithms, automata-theory, grammars
> **Comments:**
> **username_1**: You could use a standard search algorithm like $A^*$. Can you be more specific about these rules? Are they context-free?  
> **username_0**: 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...  
> **username_1**: Well, for instance, the decision problem of whether a string can be parsed by a given [context-sensitive grammar](http://en.wikipedia.org/wiki/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).  
> **username_0**: 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 :(  
> **username_2**: This looks similar to [Markov algorithms](http://en.wikipedia.org/wiki/Markov_algorithm) and [tag systems](http://en.wikipedia.org/wiki/Tag_system), which are **undecidable**.  
> **username_1**: @JɛﬀE yes, and the closely related [unrestricted grammars] are undecidable as well. But it seems that the rules here have more structure that we can exploit....  

---

## 2 answers

### Answer by username_3 on 2013-02-23. Score: 3

**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](http://people.cs.uchicago.edu/~fortnow/papers/quaderni.pdf) and a very nice paper on the [power of random strings](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.16.9225&rep=rep1&type=pdf).

> **Comments:**
> **username_1**: 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?  

---

### Answer by username_1 on 2013-02-23. Score: 1

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](http://en.wikipedia.org/wiki/CYK_algorithm) but I am not sure about the problem of smallest derivation.

---

3) Same question but for a [context-sensitive grammar](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Unrestricted_grammar). In this case, even the question of whether there exists a derivation is undecidable.

> **Comments:**
> **username_4**: 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.  
> **username_1**: @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](http://en.wikipedia.org/wiki/PPAD_\(complexity\)), except that a path is not guaranteed to exist...  
> **username_0**: 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.  
> **username_0**: Also, it is important to notice that I am not given any 'k'. I need to find the shortest.  
> **username_5**: 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.  
> **username_1**: @HommerSmith You are misunderstanding my notation (the choice of $a$ and $b$ was misleading, sorry!). I am using $a$ and $b$ to stand for arbitrary strings. I am encoding a rule as a pair $(a,b)$ where the string $a$ is transformed into the string $b$, and I am allowing the input to contain an arbitrary number of rules. Also, if we have an answer to the decision problem given a number $k$, we will probably have an answer of how to find the shortest. For example Dijkstra's finds the shortest path. Hope that is more clear?  
> **username_0**: Oh ok...I think I get it now. But with your approach, I would be able to do N transformations and I would not know when to stop. Imagine input 'a', desired output 'b', and we have a transformation that looks like 'a -> ab'. How can I know when to stop doing transformations?  
> **username_1**: @HommerSmith So here's where I'm confused. Say your only transformation is 'a -> ab'. On input 'a', is this legal: 'a -> ab -> abb -> abbb -> ...'? If so, then you have a grammar and are in case 2,3, or 4 above. If not, then you know when to stop because there are only so many possible strings you can get to before you would start cycling. (The number of such strings is 2 times the number of transformations, because you have the input and output of each transformation.) See [breadth-first search](http://en.wikipedia.org/wiki/Breadth-first_search) or Dijkstra's algorithm.  
> **username_0**: Yes, that would be legal. On first iteration you would get ab, then you would do abb, then...  
> **username_1**: @HommerSmith OK, then you are in case 2, 3, or 4 above depending on what types of rules you allow.  

---

