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.

  • 1
    $\begingroup$ Do you have any particular distribution in mind? $\endgroup$ Mar 22, 2019 at 15:34
  • 1
    $\begingroup$ Why pick $n$? Why not just expand rules randomly? At the moment, your question isn't precise enough to answer, because you've not said what distribution you want. Note that "at random" does not mean "equiprobably". $\endgroup$ Mar 22, 2019 at 16:28
  • $\begingroup$ I agree with the other comments. Foreshadowing: if you have a particular distribution in mind, a useful building block is to be able to count the number of strings of a given length; and that can be done with dynamic programming (e.g., CYK parsing). $\endgroup$
    – D.W.
    Mar 22, 2019 at 16:48
  • $\begingroup$ Does "Greibach Normal Form" have anything to do with "random"? Suppose the algorithm changes the grammar from GNF to CNF, does it matter? $\endgroup$
    – John L.
    Mar 22, 2019 at 19:55


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.