Проблема заключается в реализации алгоритма, который генерирует все строки длиной от l до r из заданной контекстно-свободной грамматики G.
Я придумал простой подход: запустить BFS на грамматическом графе, запоминая состояния. Но он не работает по некоторым рекурсивным правилам:
(1) S -> 0 | SSS | λ
Я не могу просто ограничить максимальную длину строки, потому что правила могут содержать λ (пустые строки), поэтому нетерминалы могут уменьшить окончательную длину строки. (например, при запуске (1) с l = 1, r = 2 в моей реализации будет выводить только 0)
Я также пытался ограничить максимальное количество применяемых правил, но это тоже явно неверно.
Как я могу ограничить или изменить свой алгоритм, чтобы он никогда не зацикливался и работал правильно?
