How to check if a string is obtainable using certain rules?

Question

It's been 1 week since I started trying to find a solution to this problem, and I ended up reading about CYK algorithm, but I can't understand how it would help me.

So I have a certain string from which I start, let's call it startString.
And I have a certain string to which I want to get by applying the later-explained rules, called stopString.

-----------

Now let's take an example:

startString = "A"  
stopString = "2403"

This example's rules are the following:

A->BC  
B->D  
B->ED  
C->F  
C->FB  


E->0  
D->2  
D->3  
F->4  
E->1  

The program will take the above input and output the minimal list of transformations applied to get from startString to stopString, which COULD BE the following:

A->BC, B->D, C->FB, B->ED, D->2, F->4, E->0, D->3

-----------

My question is: How does CYK help me here? How do I obtain "2403" from "A" using CYK? Is there any simpler solution to this problem?

Answer 1

I'll start by writing your grammar in Chomsky Normal Form. There are currently two rules which aren't satisfying this property; namely

B->D
C->F

A naive way to fix this is to decay them into three rules:

B->2 
B->3 
C->4

Now your production rules are

A->BC  
B->ED  
B->2 
B->3 
C->4
C->FB  
D->2  
D->3  
E->0  
E->1 
F->4  

The solver I'm using (here) doesn't allow numbers as terminals. Thus, I'll just create a bijective mapping

0 <-> a
1 <-> b
2 <-> c
3 <-> d
4 <-> e 

The new target string is "cead" instead of "2403". Plugging this into my solver yields the production rules.

Enter the start Variable A

Number of productions 11
A->BC
B->d
B->ED
C->e
C->FB
E->a
D->c
D->d
F->e
E->b
B->c

Enter string to be checked : cead
    A
          C
    A           B
   DB    CF     E    BD
String can be generated

Unfortunately, the rules are a little obscured because of the naive fix; however, I think this will suffice.