Generating Strings at Random from a Context Free Grammar
Bruce McKenzie
Department of Computer Science
University of Canterbury
Abstract
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.
Key words: Analysis of algorithms, Context-free languages, Uniform random generation, memoization.