1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Do you have any particular distribution in mind? $\endgroup$ – Yuval Filmus Mar 22 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$ – David Richerby Mar 22 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 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$ – Apass.Jack Mar 22 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.