Generating Strings at Random from a Context Free Grammar
Degree GrantorUniversity of Canterbury
Degree NameTR-COSC 10/97
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 beta where A rightarrow alpha beta is a production from the grammar. This step requires Oh(n^2) time and Oh(n^2) space. The subsequent string generation step uses these counts to generate a string in Oh(n) time and Oh(n) space.
SubjectsAnalysis of algorithms
- Engineering: Reports