I need to generate random strings given a grammar in Greibach Normal Form.
The naive approach would be to generate a random integer
n and perform
n traversals of production rules, as every traversal adds exactly one symbol to the string. The problem with this approach is that the choice of productions to expand cannot be entirely random, as some planning is required to ensure that at length
n it is possible to terminate at an empty string.