
Accession Number : AD0623002
Title : A HOMOMORPHIC THEORY OF CONTEXTFREE 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, contextfree 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. 269418, 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 contextfree 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