Tom HEAD

Finitely Generated Languages and Positive Data

 

Abstract.

From a given set of strings of symbols there are many natural schemes for generating additional strings.  Several such generative schemes are indicated here, none of which involves the use of non-terminal symbols.  A subset S of a language L generates L with respect to a given generative scheme G if no proper subset of L that contains S is closed under G.  Language classes that are closed under the action of prescribed generative schemes are studied.  Special concern is given to the generating sets of such languages.  A generating set of a language provides a basis for learning the language. When a language has a finite generating set, such a set provides an especially strong basis for learning the language.