I'm trying to solve a  CSP (Constraint-Satisfaction-Problem), which is based on arbitrary context-free grammars. A quick example: Let's say we have a context-free grammar with the following production rules: S->A, S->B, S->AB, A->Aa, A->a, A->aa, B->Bb, B->b, B->bb.Now I'm looking for a word, which uses specific (sub-sequences of) production rules. For example:S->AB must be used 3 times in the whole derivation-sequenceIf S->AB is used, it must be followed by B->Bb                                                                                 If S->Aa is used, it must directly be followed by A->aI know the problem is a CSP, but I couldnt find a specific algorithm on how to solve this. Any ideas, which (concrete) algorithm could be used? Also, I'm thinking about the right data-strucure. Should I rather use an n-Tree or an array (CYK-Table)?
CSP-problem, based on context-free grammar
graph algorithms;context free;csp