csp-алгоритм для контекстно-свободных грамматик
Я пытаюсь решить CSP (Constraint-Satisfaction-Problem), которая основана на произвольных контекстно-свободных грамматиках. Быстрый пример: допустим, у нас есть контекстно-свободная грамматика со следующими правилами производства: S->A, S->B, S->AB, A->Aa, A->a, A->aa, B->Bb, B->b, B->bb.
Теперь я ищу слово, которое использует определенные (подпоследовательности) правил производства. Например:
"B->b" 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"
Я знаю, что проблема в CSP, но я не смог найти конкретный алгоритм для решения этой проблемы. Есть идеи, какой (конкретный) алгоритм можно использовать? Кроме того, я думаю о правильной структуре данных. Стоит ли использовать n-Tree или массив (CYK-Table)?