tailieunhanh - Báo cáo khoa học: "The "Spectrum" of Weak Generative Powers of Grammars"

A summary is presented of some results in the literature concerning the generative powers of various formal grammars. The relative generative powers are displayed . Introduction Many forms of grammars have been proposed in the study of such related language problems as mechanical translation, computer languages, mathematical linguistics, and the more general characterizations of natural languages. | Mechanical Translation and Computational Linguistics March 1966 The Spectrum of Weak Generative Powers of Grammars by Wayne A. Lea Research Laboratory of Electronics Massachusetts Institute of Technology Cambridge A summary is presented of some results in the literature concerning the generative powers of various formal grammars. The relative generative powers are displayed graphically. I. Introduction Many forms of grammars have been proposed in the study of such related language problems as mechanical translation computer languages mathematical linguistics and the more general characterizations of natural languages. It is thus interesting to inquire about the relationships between such grammars. In particular one might ask which proposed grammars are the most powerful in some meaningful sense and which are the most accurate characterizations of natural-language phenomena. In this paper grammars will be compared on the basis of the possible symbol sequences they may pro-duce that is on the basis of what has been called their weak generative powers. The relationships will be displayed on a spectrum of weak generative powers of grammars. It is hoped that this concise graphical display will be found an illuminating and useful comparative summary of grammars generated languages and equivalent machines. No attempt will be made to explain in any detail the various grammars and machines listed in this paper nor will the relationships discussed be proven since they have already been considered in detail in various published papers. We shall merely consider a brief listing of each grammar language or machine type and references where each relationship to other grammars languages and machines is shown. In listing references our purpose is not to acknowledge the original developers of each interrelationship but rather only to provide references where demonstrations of such relationships can be found. Although the author does not profess to have checked that all .