Algorithms for producing grammars from sample derivations: a common problem of formal language theory and developmental biology

摘要

We give a number of algorithms which for a finite set of finite sequences of strings of symbols decide whether or not there exists a grammar of a certain fixed type such that each of the sequences is a derivation (or subderivation) by the grammar. Whenever such grammars exist, our algorithms will effectively produce one of them. The types of grammars which we consider operate by applying rules in parallel to all symbols in the strings; thus they are similar to other parallel type grammars which have been actively investigated in recent years. We restrict our attention to the types of grammars which have been found useful in modeling developmental processes in biology. In view of this, our algorithms can be considered to produce, from a finite number of observations of the development of a particular kind of organism, a model which represents the developmental rules of that organism. We discuss the relevance of our results to formal language theory and to developmental biology.