Uniform Random Generation of Balanced Parenthesis Strings

Abstract

The empirical testing of error repair schemes for skeletons of source programs in a block-structured language leads to the problem of generating balanced parenthesis strings in a uniform random manner. An efficient generator which works from left to right must compute the correct probability for the next symbol at each stage of the generation. The associated enumeration problem may be solved by adopting a geometric interpretation usually associated with random walk problems. This solution leads immediately to an O ( n ) algorithm for the generator.