Is it possible to specify an arbitrary class of equivalent programs by a finite set of sample computations? To answer this question, the notion of a generalized regular expression has been proposed to formalize the sample computations. Generalized regular expressions are an extension of ordinary regular expressions, incorporating natural numbers, assignment, and various operators and English words. They are a formalization of sample computations in the sense that any generalized regular expression describes a definite set of words that actually represent a set of sample computations of some algorithm. The generalized regular expression defining the set of all possible sample computations of a given algorithm can be regarded as a program of this algorithm. The main result is that the equivalence of two programs with similar structures can be judged by their finite sets of sample computations, which can be effectively constructed. Here the programs and sample computations are abstract and have some restrictions. The answer to the initial question is that a finite set of samples can specify a class of equivalent programs with similar structures, whereas this result is doubtful for arbitrary programs.

The paper may be of interest to researchers in program synthesis by examples. It addresses a rigorous subject, but is written in a loose style. Grammatical errors, typos, and missing labels are ubiquitous. The definition of generalized regular expressions contradicts the illustrative examples.