Generating Strings at Random from a Context Free Grammar
Type of content
Discussion / Working Papers
UC permalink
Publisher's DOI/URI
Thesis discipline
Degree name
Publisher
University of Canterbury. Computer Science and Software Engineering
Journal Title
Journal ISSN
Volume Title
Language
Date
1997
Authors
McKenzie, Bruce
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.
Description
Citation
Keywords
Analysis of algorithms, Context-free languages, Uniform random generation, memoization
Ngā upoko tukutuku/Māori subject headings
ANZSRC fields of research
Field of Research::08 - Information and Computing Sciences
Rights
Copyright Bruce McKenzie