Creating strings from context-free grammars

Question

The problem is the implementation of an algorithm that generates all the lines of length l and r from a given context free grammar G .. p>

I came up with a simple approach: run BFS on the grammar graph, remembering the states. But it doesn’t work by some recursive rules:

(1) S -> 0 | SSS | λ 

I can't just limit the maximum line length because the rules can contain λ (empty lines), so non-terminals can reduce the final line length. (for example, work (1) with l = 1 , r = 2 will only output 0 in my implementation)

I also tried to limit the maximum number of rules applied, but this is also obviously wrong.

How can I limit or change my algorithm, so it will never go into an infinite loop and will work correctly?

Answer 1

You can convert the grammar to the normal Greibach form , and then each step ¹ to createis, increasing the size of the spoken word, and you can limit the length of the word, as originally explained in the question.

---

(1), except perhaps the first, if the empty word is in the grammar