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-sequence
- If "S->AB" is used, it must be followed by "B->Bb"
- If "S->Aa" is used, it must directly be followed by "A->a"
I 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)?