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:

  1. "S->AB" must be used 3 times in the whole derivation-sequence
  2. If "S->AB" is used, it must be followed by "B->Bb"
  3. 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)?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.