A HOMOMORPHIC THEORY OF CONTEXT-FREE LANGUAGES AND ITS GENERALIZATIONS.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1965
- Accession Number
- AD0623002
Entities
People
- Yehoshafat Give'on
Organizations
- University of Michigan