'Number' Crunching Benchmark
As the code is rather long, it can be found here (Java 8): http://pastebin.com/Q5Buuqfx

How I did it:

Instead of brute-force creating the possible word combinations and then try to find a match I instead did the reverse and tried to collapse the target word to find the starting point. As a result the path the algorithm has to traverse is much less branched, and the words from the example can all be verified in about 35 ms (on my machine).

As a side-effect of the reverse-search I do not need the first two lines of each task (variables, terminals).

In addition I utilize the Java 8 streaming technology, which allows to easily activate parallel processing with just a single change in one line of code.

Usage: java Grammar &lt;inputFile&gt;

Edit: Did some code cleanup and further speed tests and it ironically turned out, that the algorithm is so fast, that setting up the parallel stream takes longer than the actual task. I now use a single-CPU stream() instead and the complete example input set is processed in ~35 ms on my machine instead of ~80 ms if I use parallelStream().

Edit2: Further testing reveals some strange effects with parallelStream and certain types of Collections. A TreeSet seems to work best in both single and parallel processing. I did some tests on your extended input set and it seems to work fine, except for the task with the looping rules (CD->DC,DC->CD). Detecting and removing those would cause the search to verify instantly.