<p>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.</p>

<p>Now I'm looking for a word, which uses specific (sub-sequences of) production rules. For example:</p>

<ol>
<li>"S->AB" must be used 3 times in the whole derivation-sequence</li>
<li>If "S->AB" is used, it must be followed by "B->Bb"                                                                                 </li>
<li>If "S->Aa" is used, it must directly be followed by "A->a"</li>
</ol>

<p>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)?</p>

CC BY-SA 3.0
2015-03-26T12:17:03.783Z
Look at controlled grammars http://en.wikipedia.org/wiki/Controlled_grammar.
Sylvain
CC BY-SA 3.0
2015-03-30T16:00:29.240Z
How do you know this is CSP? This looks more like a planning problem.
Mikolas
<graph-algorithms><context-free><csp>
CSP-problem, based on context-free grammar
Rob
# CSP-problem, based on context-free grammar

(Asked by: username_0 on 2015-03-26)

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)?

**Tags:** graph-algorithms, context-free, csp

> **Comments:**
> **username_1**: Look at controlled grammars http://en.wikipedia.org/wiki/Controlled_grammar.  
> **username_2**: How do you know this is CSP? This looks more like a planning problem.  

---

## 0 answers

