Accession Number : AD0623002

Title :   A HOMOMORPHIC THEORY OF CONTEXT-FREE LANGUAGES AND ITS GENERALIZATIONS.

Descriptive Note : Technical rept.,

Corporate Author : MICHIGAN UNIV ANN ARBOR COMMUNICATION SCIENCES PROGRAM

Personal Author(s) : Give'on,Yehoshafat

Report Date : SEP 1965

Pagination or Media Count : 29

Abstract : Usually, and naturally, context-free languages are defined and studied by means of grammars. In the course of study of these languages several algebraic characterizations were found. In this paper one of these characterizations (namely, the homomorphic characterization that was established by Chomsky and Schutzenberger (N. Chomsky and G. A. Miller. 'Introduction to Formal Analysis of Natural Languages,' 'Handbook of Mathematical Psychology, ii, J. Wiley, p. 269-418, 1963)) is regarded as the definition of this family of languages and it is shown how one can derive some of their well known properties directly from this 'redefinition.' In addition to simplification of proofs, the arguments involved lead naturally to some generalizations that have some bearing on mathematical linguistics. The families of languages derived by means of these generalizations exhibit some features which are too complex for the context-free model and yet these features are of the type that one encounters in the study of natural languages. Examples of these generalizations are discussed. (Author)

Descriptors :   (*LANGUAGE, NUMERICAL ANALYSIS), MAPPING(TRANSFORMATIONS), ALGEBRAIC TOPOLOGY, GROUPS(MATHEMATICS), SET THEORY, MONOIDS, AUTOMATA

Distribution Statement : APPROVED FOR PUBLIC RELEASE