Generating Strings at Random from a Context Free Grammar
Bruce McKenzie · UC Research Repository (University of Canterbury) · 1997
Given a context free grammar #CFG# G and an integer n #= 0 we present an algorithm for generating strings derivable from the grammar of length n such that all strings of length n are equally likely. The algorithm requires a pre-processing stage which calculates the number of strings of length k#= n derivable from each postfix # where A ! ## is a production from the grammar. This step requires O#n 2 # time and O#n 2 # space. The subsequent string generation step uses these counts to generate a string in O#n# time and O#n# space.